Consensus-Halving: Does It Ever Get Easier?

DOI10.1137/20M1387493OpenAlexW3008554935MaRDI QIDQ5890032

Aris Filos-Ratsikas, Katerina Sotiraki, Manolis Zampetakis, Alexandros Hollender

Publication date: 28 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

fair divisionTFNPPPAPPADconsensus-halving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fair and efficient cake division with connected pieces
• On total functions, existence theorems and computational complexity
• Splitting necklaces
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• 2-D Tucker is PPA complete
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Understanding PPA-completeness
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The Hairy Ball problem is PPAD-complete
• Combinatorial necklace splitting
• On the Complexity of Nash Equilibria and Other Fixed Points
• Bisection of Circle Colorings
• Settling the complexity of computing two-player Nash equilibria
• On a Topological Generalization of a Theorem of Tverberg
• Constant Rank Two-Player Games are PPAD-hard
• The Complexity of Non-Monotone Markets
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Drei Sätze über die n-dimensionale euklidische Sphäre
• Algorithmic Solutions for Envy-Free Cake Cutting
• The Complexity of Computing a Nash Equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm
• Consensus halving is PPA-complete
• A discrete and bounded envy-free cake cutting protocol for four agents
• A Moment Problem in L 1 Approximation
• Sur la division pragmatique
• The classes PPA-\(k\): existence from arguments modulo \(k\)

This page was built for publication: Consensus-Halving: Does It Ever Get Easier?