Subquadratic algorithms for succinct stable matching
DOI10.1007/s00453-019-00564-xzbMath1421.68260arXiv1510.06452OpenAlexW2923170735WikidataQ128135731 ScholiaQ128135731MaRDI QIDQ2415371
Daniel Möller, Stefan Schneider, Ramamohan Paturi, Marvin Künnemann
Publication date: 21 May 2019
Published in: Algorithmica, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.06452
single-peaked preferencesstable matchingconditional lower boundconditional lower boundsattribute modelsethsubquadratic algorithms
Analysis of algorithms (68W40) Individual preferences (91B08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Models of greedy algorithms for graph problems
- Euclidean preferences
- Geometric stable roommates
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Efficient partition trees
- On-line algorithms for weighted bipartite matching and stable marriages
- Efficient searching with linear constraints
- On the existence of stable roommate matchings
- Which problems have strongly exponential complexity?
- Stable matching with preferences derived from a psychological model
- On cores and indivisibility
- Cheating strategies for the Gale-Shapley algorithm with complete preference lists
- The communication requirements of social choice rules and supporting budget sets
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications
- Lower Bounds for the Stable Marriage Problem and Its Variants
- The Complexity of Approximately Counting Stable Matchings
- A linear algorithm for determining the separation of convex polyhedra
- An efficient algorithm for the “stable roommates” problem
- Ms. Machiavelli and the Stable Matching Problem
- The Complexity of Counting Stable Marriages
- Three Fast Algorithms for Four Problems in Stable Marriage
- The Economics of Matching: Stability and Incentives
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Faster all-pairs shortest paths via circuit complexity
- A Stable Marriage Requires Communication
- Automata, Languages and Programming
- College Admissions and the Stability of Marriage
- On the complexity of \(k\)-SAT
This page was built for publication: Subquadratic algorithms for succinct stable matching
