31 citations · 69 across the 12 of their papers we have counts for
8 papers · 1 filter
A Better-Than- Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
Michel X. Goemans, Yuchong Pan
The demand matching problem generalizes both the knapsack problem and the -matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has…
Bicriteria Approximation Algorithms for Demand Matching
Yuchong Pan, Michel X. Goemans
The demand matching problem generalizes both the knapsack problem and the -matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a c…
Shrunk subspaces via operator Sinkhorn iteration
Cole Franks, Tasuku Soma, Michel X. Goemans
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,…
Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
We study the problem of community detection in hypergraphs under a stochastic block model. Similarly to how the stochastic block model in graphs suggests studying spiked random mat…
Polynomiality for Bin Packing with a Constant Number of Item Types
Michel X. Goemans, Thomas Rothvoss
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 kn…
Symmetric Submodular Function Minimization Under Hereditary Family Constraints
Michel X. Goemans, José A. Soto
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…