Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle

DOI10.1007/978-3-540-68891-4_19MaRDI QIDQ3503853zbMATH OpenOpenAlexFDO

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

Publication date 10 June 2008

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• On Budgeted Optimization Problems
• Multi-budgeted matching problems
• Approximation Schemes for Multi-Budgeted Independence Systems
• New approaches to multi-objective optimization

Cites work

• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An algorithm for the resource constrained shortest path problem
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Generalized polymatroids and submodular flows
• scientific article; zbMATH DE number 437570 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matching is as easy as matrix inversion
• On matroid intersection adjacency
• Random pseudo-polynomial algorithms for exact matroid problems
• Real-time scheduling with a budget
• The complexity of restricted spanning tree problems
• The constrained minimum spanning tree problem

Cited in

(11)

• Approximation algorithms for maximum latency and partial cycle cover
• A theory and algorithms for combinatorial reoptimization
• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• Almost exact matchings
• Bi-criteria and approximation algorithms for restricted matchings
• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
• On Lagrangian Relaxation and Subset Selection Problems
• Multi-budgeted matching problems
• On Budgeted Optimization Problems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle

This page was built for publication: Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503853)