Optimization with More than One Budget

Details Optimization with More than One Budget Optimization with More than One Budget

2010-02-10

arxiv.org/abs/1002.2147v1

Computer Science

Data Structures and Algorithms

Scientific paper

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. Not much is known however for the case of strict budget constraints: filling this gap is the main goal of this paper. We show that shortest path, perfect matching, and spanning tree (and hence matroid basis and matroid intersection basis) are inapproximable already with two budget constraints. For the remaining problems, whose set of solutions forms an independence system, we present deterministic and randomized polynomial-time approximation schemes for a constant number k of budget constraints. Our results are based on a variety of techniques: 1. We present a simple and powerful mechanism to transform multi-criteria approximation schemes into pure approximation schemes. 2. We show that points in low dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for k-budgeted matroid independent set. 3. We present a deterministic approximation scheme for 2-budgeted matching. The backbone of this result is a purely topological property of curves in R^2.

Affiliated with

Also associated with

No associations

Rating

Optimization with More than One Budget does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimization with More than One Budget, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization with More than One Budget will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-239398