What is a bicriteria approximation algorithm?

Question

What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization?

This is where I came across it: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. The paper is about a streaming version of the k-means algorithm. There are references in the paper but none of them give an explanation as to what a bicriteria approximation algorithm is. I cannot seem to find anything on Google that will give me a precise definition either.

Answer 1

I'll expand on the answer by Yuval Filmus by providing an interpretation based on multi-objective optimization problems.

Single-objective optimization and approximation

In computer science we often study optimization problems with a single objective (for example, minimize f(x) subject to some constraint). When proving, say, NP-completeness, it is common to consider the corresponding budget problem. For example, in the maximum clique problem, the objective is to maximize the cardinality of the clique, and the budget problem is the problem of deciding whether there is a clique of size at least k, where k is given as part of the input to the problem.

When it is not possible to compute an optimal solution efficiently, as in the case of the maximum clique problem, we seek an approximation algorithm, a function that outputs a solution within a multiplicative factor of an optimal solution. You could also consider an approximation algorithm for the budget problem, a function that outputs a solution that satisfies f(x) ≥ ck in the case of a maximization problem, where c is a number less than one. In this situation, the solution may violate the hard constraint f(x) ≥ k, but the "severity" of the violation is bounded by c.

Multi-objective optimization and bi-criterion approximation

In some cases, you may want to optimize two objectives simultaneously. For a rough example, I may want to maximize my "revenue" while minimizing my "cost". In such a situation, there is no single optimal value, as there is a tradeoff between the two objectives; for more information, see the Wikipedia article on Pareto efficiency.

One way of turning a two-objective optimization problem into a single-objective optimization problem (for which we can reason about the optimal value of the objective function) is to consider the two constraint problems, one for each objective. If the problem is to simultaneously maximize f(x) while minimizing g(x), the first constraint problem is to minimize g(x) subject to the constraint f(x) ≥ k, where k is given as part of the input to this single-objective optimization problem. The second constraint problem is defined similarly.

An (α, β)-bicriteria approximation algorithm for the first constraint problem is a function that takes a budget parameter k as input and outputs a solution x such that

• $f(x) \geq \alpha k$,
• $g(x) \leq \beta g(x^*)$,

where $x^*$ is a solution that achieves the optimal value for g. A bicriteria approximation algorithm for the second constraint problem outputs a solution such that

• $f(x) \geq \alpha f(x^*)$,
• $g(x) \leq \beta \ell$,

In other words, the bicriteria approximation algorithm is simultaneously an appoximation for the budget problem in the first objective and the optimization problem in the second objective. (This definition was adapted from page four of "Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints", by Iyer and Bilmes, 2013.)

The inequalities switch directions when the objectives switch from maximum to minimum or vice versa.

Answer 2

Often, an optimization problem involves several parameters. For example, consider the problem of graph partitioning. Given a weighted graph, an integer $k$, and a parameter $\rho$, we want to partition the vertex set into $k$ parts $V_1,\ldots,V_k$ of size at most $\rho$ while minimizing the number of cut edges $E(V_1,\ldots,V_k)$ (edges connecting vertices belonging to different parts). Notice that there are two parameters here: $\rho$ and the number of cut edges.

For $f(n),g(n) \geq 1$, a $f(n),g(n)$ bicriteria approximation algorithm would output a partition $V_1,\ldots,V_k$ where each part is of size at most $f(n)\rho$, and the number of cut edges is at most $g(n)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal number of cut edges in the original problem, with the parts constrained to be at size at most $\rho$.

In other words, a bicriteria approximation algorithm achieves a certain approximation ratio while violating some constraint by some bounded amount. For an example of a bicriteria approximation algorithm for the problem just described, see this paper by the Makarychev brothers.