The complexity of splitting necklaces and bisecting ham sandwiches

The complexity of splitting necklaces and bisecting ham sandwiches

Pokaži ostale verzije (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...

Bibliografski detalji
Glavni autori:	Filos-Ratsikas, A, Goldberg, PW
Format:	Conference item
Jezik:	English
Izdano:	Association for Computing Machinery 2019

Slični predmeti

The complexity of splitting necklaces and bisecting ham sandwiches
od: Filos-Ratsikas, A, i dr.
Izdano: (2019)

The complexity of necklace splitting, consensus-halving, and discrete ham sandwich
od: Filos-Ratsikas, A, i dr.
Izdano: (2022)

Dynamic ham-sandwich cuts in the plane
od: Abbott, Timothy G., i dr.
Izdano: (2015)

On Bisecting Random Graphs
od: Bui, Thang Nguyen
Izdano: (2023)

Graph bisection algorithms
od: Bui, Thang Nguyen
Izdano: (2013)

An exact combinatorial algorithm for minimum graph bisection
od: Delling, Daniel, i dr.
Izdano: (2016)

Necklaces, Convolutions, and X+Y
od: Bremner, David, i dr.
Izdano: (2019)

Necklaces, Convolutions, and X+Y
od: Bremner, David, i dr.
Izdano: (2015)

Automorphisms of necklaces and sandpile groups
od: Duzhin, S, i dr.
Izdano: (2014)

Consensus halving is PPA-complete
od: Filos-Ratsikas, A, i dr.
Izdano: (2018)

Bisecting sparse random graphs.
od: Luczak, M, i dr.
Izdano: (2001)

On the optimal bisection of a polygon
od: Koutsoupias, E, i dr.
Izdano: (2015)

On the optimal bisection of a polygon
od: Koutsoupias, E, i dr.
Izdano: (2015)

NECKLACE SOLID-ON-SOLID MODELS OF INTERFACES AND SURFACES
od: Abraham, D, i dr.
Izdano: (1986)

Development of cooling necklace system using vortex tube
od: A. N., Esa, i dr.
Izdano: (2023)

Bisections of Mass Assignments Using Flags of Affine Spaces
od: Axelrod-Freed, Ilani, i dr.
Izdano: (2024)

Relative importance of perceptual and mnemonic variance in human temporal bisection.
od: Rodríguez-Gironés, M, i dr.
Izdano: (2001)

Dissociations in rod bisection: the effect of viewing conditions on perception and action.
od: Hughes, L, i dr.
Izdano: (2008)

Komnas HAM Dan HAM Di Bawah Rejim Otoritarian
od: Perpustakaan UGM, i-lib
Izdano: (1999)

On the complexity of equilibrium computation in first-price auctions
od: Filos-Ratsikas, A, i dr.
Izdano: (2023)

Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function
od: Scott, A, i dr.
Izdano: (2009)

The modulation of haptic line bisection by a visual illusion and optokinetic stimulation.
od: Gallace, A, i dr.
Izdano: (2007)

Truthful approximations to range voting
od: Filos-Ratsikas, A, i dr.
Izdano: (2014)

The Hamming Ball Sampler
od: Titsias, M, i dr.
Izdano: (2017)

Formation of pearl-necklace monomorphic G-quadruplexes in the human CEB25 minisatellite
od: Amrane, Samir, i dr.
Izdano: (2013)

Integrated bisect K-means and firefly algorithm for hierarchical text clustering
od: Mohammed, Athraa Jasim, i dr.
Izdano: (2016)

Social welfare in one-sided matchings: Random priority and beyond.
od: Filos-Ratsikas, A, i dr.
Izdano: (2014)

Effect of tube length on the performance of cooling necklace with vortex tube cold flow generator
od: Nur Shuhada, Adnan, i dr.
Izdano: (2024)

Luttinger liquid coupled to quantum spins: Flow equation approach to the Kondo necklace model
od: Essler, F, i dr.
Izdano: (2007)

Refleksi HAM di Indonesia
od: , Sri Soemantri Martosoewignjo
Izdano: (1998)

Performance of hamming codes with interleaving /
od: 415024 Aliza Ayob
Izdano: (2002)

Fe3O4/carbon nanofibres with necklace architecture for enhanced electrochemical energy storage
od: Grant, P, i dr.
Izdano: (2015)

Fe3O4/carbon nanofibres with necklace architecture for enhanced electrochemical energy storage
od: Fu, C, i dr.
Izdano: (2015)

Social Welfare in One-Sided Matching Mechanisms.
od: Christodoulou, G, i dr.
Izdano: (2016)

Social welfare in one-sided matching mechanisms
od: Christodoulou, G, i dr.
Izdano: (2016)

Two's company, three's a crowd: consensus-halving for a constant number of agents
od: Deligkas, A, i dr.
Izdano: (2022)

Bounds for the query complexity of approximate equilibria
od: Goldberg, PW, i dr.
Izdano: (2016)

An improved 2-agent kidney exchange mechanism
od: Caragiannis, I, i dr.
Izdano: (2012)

An improved 2-agent kidney exchange mechanism
od: Caragiannis, I, i dr.
Izdano: (2015)

Carbon necklace incorporated electroactive reservoir constructing flexible papers for advanced lithium-ion batteries
od: Du, Min, i dr.
Izdano: (2020)