Copertina

A Quadratic Lower Bound for Stable Roommates Solvability

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Rosenbaum, Will
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Data Structures and Algorithms Computer Science and Game Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
di: Cheng, Christine T., et al.
Pubblicazione: (2026)

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem
di: Glitzner, Frederik, et al.
Pubblicazione: (2024)

A Smoothed FPTAS for Equilibria in Congestion Games
di: Giannakopoulos, Yiannis
Pubblicazione: (2023)

Satisfactory Budget Division
di: Gourvès, Laurent, et al.
Pubblicazione: (2025)

Hedonic Seat Arrangement Problems
di: Bodlaender, Hans L., et al.
Pubblicazione: (2020)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

The Price of Justified Representation
di: Elkind, Edith, et al.
Pubblicazione: (2021)

Unravelling Expressive Delegations: Complexity and Normative Analysis
di: Tyrovolas, Giannis, et al.
Pubblicazione: (2023)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
di: Anagnostides, Ioannis, et al.
Pubblicazione: (2023)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
di: Kawase, Sota, et al.
Pubblicazione: (2024)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
di: Benedek, Márton, et al.
Pubblicazione: (2023)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
di: Chen, Xi, et al.
Pubblicazione: (2024)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
di: Koenemann, Jochen, et al.
Pubblicazione: (2021)

Nemesis, an Escape Game in Graphs
di: Bergé, Pierre, et al.
Pubblicazione: (2026)

Complexity of Auctions with Interdependence
di: Loiseau, Patrick, et al.
Pubblicazione: (2026)

EF1 and EFX Orientations
di: Deligkas, Argyrios, et al.
Pubblicazione: (2024)

Efficiency in the Roommates Problem
di: Kuwahara, Keita
Pubblicazione: (2025)

Partitioned Matching Games for International Kidney Exchange
di: Benedek, Márton, et al.
Pubblicazione: (2023)

Dynamic Debt Swapping in Financial Networks
di: Froese, Henri, et al.
Pubblicazione: (2023)

Stable Algorithms Lower Bounds for Estimation
di: Yu, Xifan, et al.
Pubblicazione: (2026)

On Binary Networked Public Goods Game with Altruism
di: Maiti, Arnab, et al.
Pubblicazione: (2022)

Weighted Envy Freeness With Bounded Subsidies
di: Elmalem, Noga Klein, et al.
Pubblicazione: (2024)

A Minimax Perspective on Almost-Stable Matchings
di: Glitzner, Frederik, et al.
Pubblicazione: (2026)

Risk-Sensitive Online Selection with Bounded Adaptivity
di: Nekouyan, Hossein, et al.
Pubblicazione: (2025)

Prophet Upper Bounds for Online Matching and Auctions
di: Soto, José, et al.
Pubblicazione: (2024)

Stable Matching with Interviews
di: Ashlagi, Itai, et al.
Pubblicazione: (2025)

Stable Matching with Deviators and Conformists
di: Glitzner, Frederik, et al.
Pubblicazione: (2026)

Stable Hypergraph Matching in Unimodular Hypergraphs
di: Biró, Péter, et al.
Pubblicazione: (2025)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
di: Eden, Alon, et al.
Pubblicazione: (2024)

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
di: Ezra, Tomer, et al.
Pubblicazione: (2024)

Near-Feasible Stable Matchings: Incentives and Optimality
di: Glitzner, Frederik
Pubblicazione: (2026)

Optimal Capacity Modification for Stable Matchings with Ties
di: Ranjan, Keshav, et al.
Pubblicazione: (2024)

Min-Max Optimization Requires Exponentially Many Queries
di: Bernasconi, Martino, et al.
Pubblicazione: (2026)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
di: Glitzner, Frederik, et al.
Pubblicazione: (2025)

Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
di: McCauley, Samuel, et al.
Pubblicazione: (2026)

Attractors Is All You Need: Parity Games In Polynomial Time
di: van der Heijden, Rick
Pubblicazione: (2025)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

A Strongly Polynomial Algorithm for Arctic Auctions
di: Garg, Jugal, et al.
Pubblicazione: (2026)

A Little Aggression Goes a Long Way
di: Krishnan, Jyothi, et al.
Pubblicazione: (2024)

A symmetric recursive algorithm for mean-payoff games
di: Ohlmann, Pierre
Pubblicazione: (2026)