Carnegie Mellon University
Browse
Iterative Rounding for Multi-Objective Optimization Problems.pdf.pdf' (180.75 kB)

Iterative Rounding for Multi-Objective Optimization Problems

Download (180.75 kB)
journal contribution
posted on 2011-07-01, 00:00 authored by Fabrizio Grandoni, Ramamoorthi RaviRamamoorthi Ravi, Mohit Singh
In this paper we show that iterative rounding is a powerful and flexible tool in the design of approximation algorithms for multi-objective optimization problems. We illustrate that by considering the multi-objective versions of three basic optimization problems: spanning tree, matroid basis and matching in bipartite graphs. Here, besides the standard weight function, we are given k length functions with corresponding budgets. The goal is finding a feasible solution of maximum weight and such that, for all i, the ith length of the solution does not exceed the ith budget. For these problems we present polynomial-time approximation schemes that, for any constant ε>  0 and k ≥ 1, compute a solution violating each budget constraint at most by a factor (1 + ε). The weight of the solution is optimal for the first two problems, and (1 − ε)-approximate for the last one.

History

Publisher Statement

All Rights Reserved

Date

2011-07-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC