The Demand-Matching Problem

DOI10.1287/moor.1070.0254zbMath1341.90117OpenAlexW2160146903MaRDI QIDQ5388047

F. Bruce Shepherd, Adrian Vetta

Publication date: 27 May 2008

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1070.0254

zbMATH Keywords

linear programmingapproximation algorithm\(b\)-matchingintegrality gap

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Matching models (91B68)

Related Items (8)

Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ Stochastic packing integer programs with few queries ⋮ Unnamed Item ⋮ Approximability of sparse integer programs ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Unnamed Item

This page was built for publication: The Demand-Matching Problem