Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
type: Item
instance of: scholarly article
title: Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
DOI: 10.1007/978-3-030-92702-8_4
author: Szymon Dudycz
author: Pasin Manurangsi
author: Jan Marcinkowski
publication date: 2022-10-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7603884
zbMATH Keywords: matching
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
full work available at URL: 978-3-030-92702-8 4
OpenAlex ID: W4285543569
cites work: Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
cites work: Optimal Long Code Test with One Free Bit
cites work: Bicovering: Covering edges with two small subsets of vertices
cites work: Q2753930
cites work: Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
cites work: Approximation hardness of edge dominating set problems
cites work: On non-optimally expanding sets in Grassmann graphs
cites work: Towards a proof of the 2-to-1 games conjecture?
cites work: Tight approximation ratio for Minimum Maximal Matching
cites work: New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set
cites work: A 2-approximation algorithm for the minimum weight edge dominating set problem
cites work: A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
cites work: A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
cites work: On the power of unique 2-prover 1-round games
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
cites work: Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
cites work: Q4828945
cites work: Graph expansion and the unique games conjecture
cites work: Approximating edge dominating set in dense graphs
cites work: Edge Dominating Sets in Graphs
description: scientific article; zbMATH DE number 7603884