The complexity of splitting necklaces and bisecting ham sandwiches

The complexity of splitting necklaces and bisecting ham sandwiches

Taispeáin leaganacha eile (1)

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 r...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Filos-Ratsikas, A, Goldberg, PW
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2019

Míreanna comhchosúla

The complexity of splitting necklaces and bisecting ham sandwiches
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2019)

The complexity of necklace splitting, consensus-halving, and discrete ham sandwich
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2022)

Dynamic ham-sandwich cuts in the plane
de réir: Abbott, Timothy G., et al.
Foilsithe / Cruthaithe: (2015)

On Bisecting Random Graphs
de réir: Bui, Thang Nguyen
Foilsithe / Cruthaithe: (2023)

Graph bisection algorithms
de réir: Bui, Thang Nguyen
Foilsithe / Cruthaithe: (2013)

An exact combinatorial algorithm for minimum graph bisection
de réir: Delling, Daniel, et al.
Foilsithe / Cruthaithe: (2016)

Necklaces, Convolutions, and X+Y
de réir: Bremner, David, et al.
Foilsithe / Cruthaithe: (2019)

Necklaces, Convolutions, and X+Y
de réir: Bremner, David, et al.
Foilsithe / Cruthaithe: (2015)

Automorphisms of necklaces and sandpile groups
de réir: Duzhin, S, et al.
Foilsithe / Cruthaithe: (2014)

Consensus halving is PPA-complete
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2018)

Bisecting sparse random graphs.
de réir: Luczak, M, et al.
Foilsithe / Cruthaithe: (2001)

On the optimal bisection of a polygon
de réir: Koutsoupias, E, et al.
Foilsithe / Cruthaithe: (2015)

On the optimal bisection of a polygon
de réir: Koutsoupias, E, et al.
Foilsithe / Cruthaithe: (2015)

NECKLACE SOLID-ON-SOLID MODELS OF INTERFACES AND SURFACES
de réir: Abraham, D, et al.
Foilsithe / Cruthaithe: (1986)

Development of cooling necklace system using vortex tube
de réir: A. N., Esa, et al.
Foilsithe / Cruthaithe: (2023)

Bisections of Mass Assignments Using Flags of Affine Spaces
de réir: Axelrod-Freed, Ilani, et al.
Foilsithe / Cruthaithe: (2024)

Relative importance of perceptual and mnemonic variance in human temporal bisection.
de réir: Rodríguez-Gironés, M, et al.
Foilsithe / Cruthaithe: (2001)

Dissociations in rod bisection: the effect of viewing conditions on perception and action.
de réir: Hughes, L, et al.
Foilsithe / Cruthaithe: (2008)

Komnas HAM Dan HAM Di Bawah Rejim Otoritarian
de réir: Perpustakaan UGM, i-lib
Foilsithe / Cruthaithe: (1999)

On the complexity of equilibrium computation in first-price auctions
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2023)

Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function
de réir: Scott, A, et al.
Foilsithe / Cruthaithe: (2009)

The modulation of haptic line bisection by a visual illusion and optokinetic stimulation.
de réir: Gallace, A, et al.
Foilsithe / Cruthaithe: (2007)

Truthful approximations to range voting
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2014)

The Hamming Ball Sampler
de réir: Titsias, M, et al.
Foilsithe / Cruthaithe: (2017)

Formation of pearl-necklace monomorphic G-quadruplexes in the human CEB25 minisatellite
de réir: Amrane, Samir, et al.
Foilsithe / Cruthaithe: (2013)

Integrated bisect K-means and firefly algorithm for hierarchical text clustering
de réir: Mohammed, Athraa Jasim, et al.
Foilsithe / Cruthaithe: (2016)

Social welfare in one-sided matchings: Random priority and beyond.
de réir: Filos-Ratsikas, A, et al.
Foilsithe / Cruthaithe: (2014)

Effect of tube length on the performance of cooling necklace with vortex tube cold flow generator
de réir: Nur Shuhada, Adnan, et al.
Foilsithe / Cruthaithe: (2024)

Luttinger liquid coupled to quantum spins: Flow equation approach to the Kondo necklace model
de réir: Essler, F, et al.
Foilsithe / Cruthaithe: (2007)

Refleksi HAM di Indonesia
de réir: , Sri Soemantri Martosoewignjo
Foilsithe / Cruthaithe: (1998)

Performance of hamming codes with interleaving /
de réir: 415024 Aliza Ayob
Foilsithe / Cruthaithe: (2002)

Fe3O4/carbon nanofibres with necklace architecture for enhanced electrochemical energy storage
de réir: Grant, P, et al.
Foilsithe / Cruthaithe: (2015)

Fe3O4/carbon nanofibres with necklace architecture for enhanced electrochemical energy storage
de réir: Fu, C, et al.
Foilsithe / Cruthaithe: (2015)

Social Welfare in One-Sided Matching Mechanisms.
de réir: Christodoulou, G, et al.
Foilsithe / Cruthaithe: (2016)

Social welfare in one-sided matching mechanisms
de réir: Christodoulou, G, et al.
Foilsithe / Cruthaithe: (2016)

Two's company, three's a crowd: consensus-halving for a constant number of agents
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2022)

Bounds for the query complexity of approximate equilibria
de réir: Goldberg, PW, et al.
Foilsithe / Cruthaithe: (2016)

An improved 2-agent kidney exchange mechanism
de réir: Caragiannis, I, et al.
Foilsithe / Cruthaithe: (2012)

An improved 2-agent kidney exchange mechanism
de réir: Caragiannis, I, et al.
Foilsithe / Cruthaithe: (2015)

Carbon necklace incorporated electroactive reservoir constructing flexible papers for advanced lithium-ion batteries
de réir: Du, Min, et al.
Foilsithe / Cruthaithe: (2020)