Source author record

Michel X. Goemans

Michel X. Goemans appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics math.CO

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Shrunk subspaces via operator Sinkhorn iteration

A recent breakthrough in Edmonds' problem showed that the noncommutative rank can be computed in deterministic polynomial time, and various algorithms for it were devised. However, only quite complicated algorithms are known for finding a so-called shrunk subspace, which acts as a dual certificate for the value of the noncommutative rank. In particular, the operator Sinkhorn algorithm, perhaps the simplest algorithm to compute the noncommutative rank with operator scaling, does not find a shrunk subspace. Finding a shrunk subspace plays a key role in applications, such as separation in the Brascamp-Lieb polytope, one-parameter subgroups in the null-cone membership problem, and primal-dual algorithms for matroid intersection and fractional matroid matching. In this paper, we provide a simple Sinkhorn-style algorithm to find the smallest shrunk subspace over the complex field in deterministic polynomial time. To this end, we introduce a generalization of the operator scaling problem, where the spectra of the marginals must be majorized by specified vectors. Then we design an efficient Sinkhorn-style algorithm for the generalized operator scaling problem. Applying this to the shrunk subspace problem, we show that a sufficiently long run of the algorithm also finds an approximate shrunk subspace close to the minimum exact shrunk subspace. Finally, we show that the approximate shrunk subspace can be rounded if it is sufficiently close. Along the way, we also provide a simple randomized algorithm to find the smallest shrunk subspace. As applications, we design a faster algorithm for fractional linear matroid matching and efficient weak membership and optimization algorithms for the rank-2 Brascamp-Lieb polytope.

preprint2020arXiv

Polynomiality for Bin Packing with a Constant Number of Item Types

We consider the bin packing problem with d different item sizes s_i and item multiplicities a_i, where all numbers are given in binary encoding. This problem formulation is also known as the 1-dimensional cutting stock problem. In this work, we provide an algorithm which, for constant d, solves bin packing in polynomial time. This was an open problem for all d >= 3. In fact, for constant d our algorithm solves the following problem in polynomial time: given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.

preprint2011arXiv

Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem - one that heavily exploits methods and results from the theory of matroids and submodular functions - which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap. Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs. For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.

preprint2010arXiv

Symmetric Submodular Function Minimization Under Hereditary Family Constraints

We present an efficient algorithm to find non-empty minimizers of a symmetric submodular function over any family of sets closed under inclusion. This for example includes families defined by a cardinality constraint, a knapsack constraint, a matroid independence constraint, or any combination of such constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular function where $n$ is the cardinality of the ground set. In contrast, the problem of minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $o(\sqrt{n/\log n})$ (Svitkina and Fleischer [2008]). The algorithm is similar to an algorithm of Nagamochi and Ibaraki [1998] to find all nontrivial inclusionwise minimal minimizers of a symmetric submodular function over a set of cardinality $n$ using $O(n^3)$ oracle calls. Their procedure in turn is based on Queyranne's algorithm [1998] to minimize a symmetric submodular