Subquadratic algorithms for succinct stable matching
type: Item
instance of: scholarly article
title: Subquadratic algorithms for succinct stable matching
title: Subquadratic Algorithms for Succinct Stable Matching
zbMATH Open document ID: 1421.68260
zbMATH Open document ID: 1475.68476
DOI: 10.1007/978-3-319-34171-2_21
DOI: 10.1007/S00453-019-00564-X
author: Marvin Künnemann
author: Daniel Möller
author: Ramamohan Paturi
author: Stefan Schneider
published in: Algorithmica
published in: Computer Science – Theory and Applications
publication date: 2019-05-21T00:00:00Z
publication date: 2016-07-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1510.06452
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 91B08
Mathematics Subject Classification ID: 91B68
zbMATH DE Number: 7057347
zbMATH DE Number: 6605935
zbMATH Keywords: stable matching
zbMATH Keywords: attribute model
zbMATH Keywords: subquadratic algorithms
zbMATH Keywords: conditional lower bound
zbMATH Keywords: seth
zbMATH Keywords: single-peaked preferences
zbMATH Keywords: conditional lower bounds
MaRDI profile type: Publication
OpenAlex ID: W2923170735
OpenAlex ID: W3098709746
arXiv ID: 1510.06452
cites work: Q4225298
cites work: Geometric stable roommates
cites work: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
cites work: Stable matching with preferences derived from a psychological model
cites work: Q3579506
cites work: Euclidean preferences
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: The Complexity of Approximately Counting Stable Matchings
cites work: A linear algorithm for determining the separation of convex polyhedra
cites work: College Admissions and the Stability of Marriage
cites work: A Stable Marriage Requires Communication
cites work: Q3995616
cites work: A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Efficient partition trees
cites work: Lower Bounds for the Stable Marriage Problem and Its Variants
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q3999327
cites work: The communication requirements of social choice rules and supporting budget sets
cites work: Automata, Languages and Programming
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: Efficient searching with linear constraints
cites work: On the existence of stable roommate matchings
cites work: Models of greedy algorithms for graph problems
cites work: Ms. Machiavelli and the Stable Matching Problem
cites work: Three Fast Algorithms for Four Problems in Stable Marriage
cites work: An efficient algorithm for the “stable roommates” problem
cites work: The Complexity of Counting Stable Marriages
cites work: On-line algorithms for weighted bipartite matching and stable marriages
cites work: Cheating strategies for the Gale-Shapley algorithm with complete preference lists
cites work: Q5417690
cites work: The Economics of Matching: Stability and Incentives
cites work: On cores and indivisibility
cites work: Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications
cites work: Q5368736
Wikidata QID: Q128135731
Recommended article: Q3128926
Recommended article: A sublinear parallel algorithm for stable matching
Recommended article: Sublinear Algorithms for Parameterized Matching
Recommended article: Faster and Simpler Approximation of Stable Matchings
Recommended article: Faster and simpler approximation of stable matchings
Recommended article: Sublinear-Time Parallel Algorithms for Matching and Related Problems
Recommended article: Maximal matching stabilizes in quadratic time
Recommended article: A faster algorithm for the Strongly Stable \(b\)-Matching Problem

Subquadratic algorithms for succinct stable matching (Recommended article)
Recommended article: Subquadratic algorithms for succinct stable matching
Similarity Score: 1.0000004
Recommender Run: Recommender Run 3