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

DOI10.1016/J.DAM.2015.01.008MaRDI QIDQ499331zbMATH OpenOpenAlexFDO

Authors Maksim Barketau, Erwin Pesch, Y. 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

approximation algorithmbipartite graphmaximal matchingnon-approximabilityNP-hardness in the strong sense

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
• A weighted perfect matching with constraints on weights of its parts
• Theory and Applications of Models of Computation
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• The partitioning min-max weighted matching problem

Cites work

• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Algorithm for the solution of the bottleneck assignment problem
• An augmenting path method for solving linear bottleneck assignment problems
• Assignment Problems
• Determining crane areas in intermodal transshipment yards: the yard partition problem
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

Cited in

(12)

• Crossing minimization in weighted bipartite graphs
• Bottleneck subset-type restricted matching problems
• Solving the single crane scheduling problem at rail transshipment yards
• Optimum matchings in weighted bipartite graphs
• The partitioning min-max weighted matching problem
• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
• A weighted perfect matching with constraints on weights of its parts
• Crossing Minimization in Weighted Bipartite Graphs
• Scheduling dedicated jobs with variative processing times
• Socially fair matching: exact and approximation algorithms
• Fair and efficient graphical resource allocation with matching-induced utilities
• Multiple parallel-batch machines scheduling with additive resource assignment and machine available times

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

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