Weighted matching with pair restrictions

DOI10.1007/s11590-017-1217-7zbMath1400.90259OpenAlexW2769457681MaRDI QIDQ1749789

Dorit S. Hochbaum, Asaf Levin

Publication date: 28 May 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1217-7

zbMATH Keywords

traveling salesman problemassignmentgammoidmatching matroidprize collectingweighted graph matchingweighted matroid parity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (1)

Selecting intervals to optimize the design of observational studies subject to fine balance constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• An augmenting path algorithm for linear matroid parity
• Solving school bus routing using the multiple vehicle traveling purchaser problem: a branch-and-cut approach
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• Algebraic Algorithms for Linear Matroid Parity Problems
• Matroid Matching: The Power of Local Search
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• The prize collecting traveling salesman problem
• Random pseudo-polynomial algorithms for exact matroid problems
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: Weighted matching with pair restrictions