What is a bicriteria approximation algorithm?
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.