Publication

Hardness Results for Consensus-Halving

2018
Conference Papers

Résumé

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 epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in that the problem of computing an epsilon-approximate consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon 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.

Source officielle

https://infoscience.epfl.ch/entities/publication/9fcce6d5-1247-4c5f-a136-b6754d6530c5

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2018
Conference Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/9fcce6d5-1247-4c5f-a136-b6754d6530c5

À propos de ce résultat

Concepts associés (32)

NP-difficile

vignette|300px|Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet.

Problème NP-complet

En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l

Problème de décision

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.

Afficher plus

Publications associées (3)

Hardness Results for Consensus-Halving

Chattez avec Graph Search

The Tactical Berth Allocation Problem (TBAP) with quay crane assignment and transshipment-related quadratic yard costs

Variations of split-coloring in permutation graphs

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications