Hardness results for consensus-halving

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Aris Filos-Ratsikas, École Polytechnique Fédérale de Lausanne
  • ,
  • Søren Kristoffer Stiil Frederiksen
  • ,
  • Paul W. Goldberg, Oxford University, Oxford, UK.
  • ,
  • Jie Zhang, University of Southampton

The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the -approximate version, which allows each agent to have an discrepancy on the values of the portions. It was recently proven in [13] that the problem of computing an -approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when is inverse-exponential. In this paper, we prove that when is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard.

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
EditorsIgor Potapov, James Worrell, Paul Spirakis
Volume117
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year1 Aug 2018
Article number24
ISBN (print)9783959770866
DOIs
Publication statusPublished - 1 Aug 2018
Event43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom
Duration: 27 Aug 201831 Aug 2018

Conference

Conference43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
LandUnited Kingdom
ByLiverpool
Periode27/08/201831/08/2018

    Research areas

  • Consensus halving, Generalized-circuit, PPA, PPAD, Reduction

See relations at Aarhus University Citationformats

ID: 143264545