Budgeted matching and budgeted matroid intersection via the gasoline puzzle

DOI10.1007/s10107-009-0307-4zbMath1223.05222MaRDI QIDQ543415

Vincenzo Bonifaci, Fabrizio Grandoni, André Berger, Guido Schäfer

Publication date: 17 June 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/14736

zbMATH Keywords

Lagrangian relaxation; matching; matroid intersection; budgeted optimization

Mathematics Subject Classification ID

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05B35: Combinatorial aspects of matroids and geometric lattices

68R99: Discrete mathematics in relation to computer science