Minimizing maximum weight of subsets of a maximum matching in a bipartite graph

DOI10.1016/j.dam.2015.01.008zbMath1321.05198OpenAlexW1965881248MaRDI QIDQ499331

Maksim Barketau, Erwin Pesch, Yakov M. Shafransky

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.01.008

zbMATH Keywords

bipartite graphapproximation algorithmmaximal matchingnon-approximabilityNP-hardness in the strong sense

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (6)

The partitioning min-max weighted matching problem ⋮ A weighted perfect matching with constraints on weights of its parts ⋮ Solving the single crane scheduling problem at rail transshipment yards ⋮ Socially fair matching: exact and approximation algorithms ⋮ Bottleneck subset-type restricted matching problems ⋮ Scheduling dedicated jobs with variative processing times

Cites Work

• Unnamed Item
• Algorithm for the solution of the bottleneck assignment problem
• An augmenting path method for solving linear bottleneck assignment problems
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Determining crane areas in intermodal transshipment yards: the yard partition problem
• Assignment Problems
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

This page was built for publication: Minimizing maximum weight of subsets of a maximum matching in a bipartite graph