Consensus-Halving: Does It Ever Get Easier?

DOI10.1137/20M1387493MaRDI QIDQ5890032zbMATH OpenOpenAlexFDO

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

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

consensus-halvingfair divisionPPAPPADTFNP

Mathematics Subject Classification ID

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

Recommendations

• Consensus halving is PPA-complete
• Consensus halving for sets of items
• Consensus Halving for Sets of Items
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Hardness results for consensus-halving
• Uniform consensus is harder than consensus
• Distributed consensus, revisited
• Distributed consensus revisited
• When consensus meets self-stabilization
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem

Cites work

• 2-D Tucker is PPA complete
• A discrete and bounded envy-free cake cutting protocol for four agents
• A Moment Problem in L 1 Approximation
• A Sperner lemma complete for PPA
• Algorithmic solutions for envy-free cake cutting
• Bisection of Circle Colorings
• Combinatorial necklace splitting
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Consensus halving is PPA-complete
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Constant rank two-player games are PPAD-hard
• Drei Sätze über die n-dimensionale euklidische Sphäre
• Fair and efficient cake division with connected pieces
• Hardness results for consensus-halving
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• scientific article; zbMATH DE number 3097423 (Why is no real title available?)
• scientific article; zbMATH DE number 3102257 (Why is no real title available?)
• On a Topological Generalization of a Theorem of Tverberg
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Settling the complexity of computing two-player Nash equilibria
• Splitting necklaces
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Sur la division pragmatique
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The complexity of computing a Nash equilibrium
• The Complexity of Non-Monotone Markets
• The complexity of splitting necklaces and bisecting ham sandwiches
• The Hairy Ball problem is PPAD-complete
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Understanding PPA-completeness

Cited in

(5)

• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• The chromatic number of Kneser hypergraphs via consensus division
• The chromatic number of Kneser hypergraphs via consensus division
• Ordinal maximin guarantees for group fair division
• Constant inapproximability for PPA

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890032)