Local ratio with negative weights.

DOI10.1016/j.orl.2004.02.001zbMath1054.90045OpenAlexW1979270874MaRDI QIDQ703278

Dror Rawitz, Reuven Bar Yehuda

Publication date: 11 January 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.02.001

zbMATH Keywords

MatchingAssignment problemLocal RatioMaximum flowPrimal-duals-t Cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Discrete location and assignment (90B80)

Related Items (2)

Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem ⋮ Combination of parallel machine scheduling and vertex cover

Cites Work

• One for the price of two: a unified approach for approximating covering problems
• From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems
• Maximal Flow Through a Network
• Algorithms for the Assignment and Transportation Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Local ratio with negative weights.