We consider the problem of maximizing a nonnegative submodular set function $f:2 perpendicular \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints ...including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.
Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are ...contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings, which has a balancedness of 0.4762. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. More precisely, we obtain a balancedness of 0.4326, improving on a prior 0.1997-balanced scheme. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include ...global mininmum cuts, minimum
s
–
t
cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to
r
modulo
m
, for some integers
r
and
m
. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger’s celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus
m
. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the
k
-Center problem in this spirit are Colorful
k
...-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust
k
-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional
k
-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful
k
-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust
k
-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful
k
-Center admits no approximation algorithm with finite approximation guarantee, assuming that
P
≠
NP
. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited ...violations of the constraints of the other matroids. In addition to the classical steps of iterative relaxation approaches, we iteratively
refine
involved matroid constraints. This leads to more restrictive constraint systems whose structure can be exploited to prove the existence of constraints that can be dropped. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation and rounding methods, which typically involve a single matroid polytope with additional simple cardinality constraints that do not overlap too much. We show that our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.
Submodular function minimization (SFM) is a fundamental and efficiently solvable problem in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only ...very little known about constraint types under which SFM remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial SFM algorithms are known are parity constraints, i.e., optimizing only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants are bounded by two in absolute value.
We show that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we can show that effi- cient SFM is possible over all sets (of any given lattice) of cardinality
r
mod
m
, as long as
m
is a constant prime power. This covers generalizations of the odd-cut problem with open complexity status, and has interesting links to integer programming with bounded subdeterminants. To obtain our results, we establish a connection between the correctness of a natural algorithm, and the nonexistence of set systems with specific combinatorial properties. We introduce a general technique to disprove the existence of such set systems, which allows for obtaining extensions of our results beyond the above-mentioned setting. These extensions settle two open questions raised by Geelen and Kapadia 9 in the context of computing the girth and cogirth of certain types of binary matroids.
Matroids Are Immune to Braess’ Paradox Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias ...
Mathematics of operations research,
08/2017, Letnik:
42, Številka:
3
Journal Article
Recenzirano
Odprti dostop
The famous Braess paradox describes the counterintuitive phenomenon in which, in certain settings, an increase of resources, such as a new road built within a congested network, may in fact lead to ...larger costs for the players in an equilibrium. In this paper, we consider general nonatomic congestion games and give a characterization of the combinatorial property of strategy spaces for which the Braess paradox does not occur. In short,
matroid bases
are precisely the required structure. We prove this characterization by two novel sensitivity results for convex separable optimization problems over polymatroid base polyhedra, which may be of independent interest.
We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph
G
with positive weights on its ...edges. In the edge interdiction problem, every edge of
G
has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of
min
–
max
problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique.
We consider the problem of maximally decreasing the edge-connectivity of an edge-weighted graph by removing a limited set of edges. This problem, which we term connectivity interdiction, falls into a ...large family of so-called interdiction problems, which have been considered in a variety of contexts. Whereas little is known about the approximability of most interdiction problems, we show that connectivity interdiction admits a PTAS, and a natural special case of it can even be solved efficiently.
PDF
