Optimization with More than One Budget

Understand

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints.

• Some classical polynomial-time optimization problems, such as spanning tree and forest, shortest path, (perfect) matching, independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint.
• Still, for most of these problems deterministic and randomized polynomial-time approximation schemes are known.
• In the case of two or more budgets, typically only multi-criteria approximation schemes are available, which return slightly infeasible solutions.