Combinatorial optimization I
Org: Tamon Stephen
(Simon Fraser University)
- MEHRDAD GHADIRI, University of British Columbia
In Search of Tractable Supermodular Maximization Problems [PDF]
Despite many applications, supermodular maximization has received much less attention than its submodular counter-part due in part to its intractability. Nevertheless certain special cases, such as metric diversity, are known to have good algorithmic properties. We introduce a parameterized class of functions called meta-submodular that can be approximately maximized within a constant factor. Our class includes both metric diversity, monotone submodular and other functions appearing in the machine learning and optimization literature. Tractability appears to stem from an intrinsic one-sided smoothness property for their multi-linear extensions. We believe this smoothness property is of independent interest.
- KANSTANTSIN PASHKOVICH, University of Ottawa
On the approximability of the stable matching problem with ties of size two [PDF]
The stable matching problem is central for game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. We give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor.
Joint work with Robert Chiang.
- CHARLES VISS, University of Colorado, Denver
A Polyhedral Model for Enumeration and Optimization over the Set of Circuits [PDF]
Circuits play a fundamental role in linear programming. For instance, circuits are the step directions in various augmentation schemes for linear programs. Significant challenges lie in the possibly exponential size of the set of circuits of a polyhedron and the sensitivity to its representation.
We devise a universal framework for enumeration over the set of circuits: a polyhedron in which the circuits appear as vertices. This enables the direct enumeration of specific subsets of circuits, as well as optimization over circuits. This leads to the efficient computation of steepest-descent circuit directions and the construction of conformal sums with additional properties.
- AMY WIEBE, University of Washington
Slack Realization Spaces [PDF]
In this talk we discuss an ideal associated to a polytope called its slack ideal and show how this ideal can be used to create a new model for studying realization spaces. These ideals were first introduced to study PSD rank of polytopes, and we show how their structure encodes other important combinatorial properties. We also present an extension of the model to the setting of matroids.