31 citations · 69 across the 12 of their papers we have counts for
Showing 2026 · cs.DSShow all
2 papers · 2 filters
cs.DS2026
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…
cs.DS2026
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…