On maximum bipartite matching with separation

DOI10.1016/J.IPL.2023.106388MaRDI QIDQ6161448zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong

Publication date 5 June 2023

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2303.02283

zbMATH Keywords

approximation algorithmsbipartite matchingseparation constraint

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the vertices on one side lie on a path or a grid, and two vertices that are close to each other are not allowed to be matched simultaneously. We show that the problem is hard to approximate even for paths, and provide constant-factor approximation algorithms for both paths and grids.

Recommendations

• Maximum semi-matching problem in bipartite graphs
• A decomposition theorem for maximum weight bipartite matchings
• On maximum induced matchings in bipartite graphs
• On the Bipartite Unique Perfect Matching Problem
• On bipartite matchings of minimum density
• On maximal bipartite matching extendable graphs
• On the computational complexity of the bipartizing matching problem
• On the maximum edge-pair embedding bipartite matching
• On the maximum edge-pair embedding bipartite matching
• Bounds on maximum \(b\)-matchings

Cites work

• A note on scheduling equal-length jobs to maximize throughput
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximating the k-set packing problem by local improvements
• How to sell hyperedges: the hypermatching assignment problem
• Independent systems of representatives in weighted graphs
• Introduction to algorithms.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Losing Treewidth by Separating Subsets
• Mind the gap: cake cutting with separation
• On Forming Committees
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

Cited in

(6)

• Minimum transversals of maximum matchings as approximate solutions to the bisection problem
• On the computational complexity of the bipartizing matching problem
• A decomposition theorem for maximum weight bipartite matchings
• scientific article; zbMATH DE number 2185638 (Why is no real title available?)
• Stability in graphs with matroid constraints
• Cuts in graphs with matroid constraints

This page was built for publication: On maximum bipartite matching with separation

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