New approaches to multi-objective optimization

Grandoni, Fabrizio and Ravi, R. and Singh, Mohit and Zenklusen, Rico (2014) New approaches to multi-objective optimization. Mathematical Programming, 146 (1-2). pp. 525-554. ISSN 0025-5610

Full text not available from this repository.


A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight 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 efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with

Actions (login required)

View Item View Item