Budgeted matching and budgeted matroid intersection via the gasoline puzzle

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

Vincenzo Bonifaci, André Berger, Fabrizio Grandoni, 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 relaxationmatchingmatroid intersectionbudgeted optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Discrete mathematics in relation to computer science (68R99)

Related Items (19)

Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ New approaches to multi-objective optimization ⋮ On the complexity and approximation of the maximum expected value all-or-nothing subset ⋮ Obtaining approximately optimal and diverse solutions via dispersion ⋮ Socially fair matching: exact and approximation algorithms ⋮ Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines ⋮ Unnamed Item ⋮ Multi-criteria TSP: Min and Max combined ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Budgeted colored matching problems ⋮ Bi-objective matchings with the triangle inequality ⋮ Discrete representation of the non-dominated set for multi-objective optimization problems using kernels ⋮ Unnamed Item ⋮ On a cardinality-constrained transportation problem with market choice ⋮ Bulk-robust combinatorial optimization ⋮ Generalized Center Problems with Outliers ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Approximate tradeoffs on weighted labeled matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real-time scheduling with a budget
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• Generalized polymatroids and submodular flows
• The dependence graph for bases in matroids
• On certain polytopes associated with graphs
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Approximating minimum bounded degree spanning trees to within one of optimal
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• An algorithm for the resource constrained shortest path problem
• Combinatorial Optimization with Rational Objective Functions
• The complexity of restricted spanning tree problems
• Random pseudo-polynomial algorithms for exact matroid problems
• Bicriteria Network Design Problems
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Many birds with one stone
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• On matroid intersection adjacency

This page was built for publication: Budgeted matching and budgeted matroid intersection via the gasoline puzzle