Submodular problems - approximations and algorithms

Details Submodular problems - approximations and algorithms Submodular problems - approximations and algorithms

2010-10-10

arxiv.org/abs/1010.1945v1

Computer Science

Discrete Mathematics

14 pages, 1 figure

Scientific paper

We show that any submodular minimization (SM) problem defined on a linear constraint set with constraints having up to two variables per inequality, are 2-approximable in polynomial time. If the constraints are monotone (the two variables appear with opposite sign coefficients) then the problems of submodular minimization or supermodular maximization are polynomial time solvable. The key idea is to link these problems to a submodular s,t-cut problem defined here. This framework includes the problems: SM-vertex cover; SM-2SAT; SM-min satisfiability; SM-edge deletion for clique, SM-node deletion for biclique and others. We also introduce here the submodular closure problem and and show that it is solvable in polynomial time and equivalent to the submodular cut problem. All the results are extendible to multi-sets where each element of a set may appear with a multiplicity greater than 1. For all these NP-hard problems 2-approximations are the best possible in the sense that a better approximation factor cannot be achieved in polynomial time unless NP=P. The mechanism creates a relaxed "monotone" problem, solved as a submodular closure problem, the solution to which is mapped to a half integral super-optimal solution to the original problem. That half-integral solution has the persistency property meaning that integer valued variables retain their value in an optimal solution. This permits to delete the integer valued variables, and restrict the search of an optimal solution to the smaller set of remaining variables.

Affiliated with

Also associated with

No associations

Rating

Submodular problems - approximations and algorithms 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 Submodular problems - approximations and algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular problems - approximations and algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88282