The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional M\"obius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast Clustering of Categorical Big Data
The K-Modes algorithm, developed for clustering categorical data, is of high algorithmic simplicity but suffers from unreliable performances in clustering quality and clustering efficiency, both heavily influenced by the…
ClusteringThe Fewer Splits are Better: Deconstructing Readability in Sentence Splitting
In this work, we focus on sentence splitting, a subfield of text simplification, motivated largely by an unproven idea that if you divide a sentence in pieces, it should become easier to understand. Our primary goal in t…
SentenceText SimplificationRethinking Divisive Hierarchical Clustering from a Distributional Perspective
We uncover that current objective-based Divisive Hierarchical Clustering (DHC) methods produce a dendrogram that does not have three desired properties i.e., no unwarranted splitting, group similar clusters into a same s…
Ontology Based Document Clustering Using MapReduce
Nowadays, document clustering is considered as a data intensive task due to the dramatic, fast increase in the number of available documents. Nevertheless, the features that represent those documents are also too large. …
ClusteringAn Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means
This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e.g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores resu…
Clustering