scientific article; zbMATH DE number 7662165

Publication date: 10 March 2023

Full work available at URL: https://arxiv.org/abs/2109.06752

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity computational geometry ham-sandwich theorem PPA pizza sharing

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

Unnamed Item
Unnamed Item
Computing generalized ham-sandwich cuts
Balanced partitions of 3-colored geometric sets in the plane
Generalized ham-sandwich cuts
The complexity of equilibria: Hardness results for economies via a correspondence with games
Splitting necklaces
On the complexity of the parity argument and other inefficient proofs of existence
Algorithms for ham-sandwich cuts
Computing balanced islands in two colored point sets in the plane
Unique end of potential line
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
Ham-sandwich cuts and center transversals in subspaces
Bisecting three classes of lines
Slicing convex sets and measures by a hyperplane
Complexity results on restricted instances of a paint shop problem for words
Measure partitions using hyperplanes with fixed directions
Generalized sandwich theorems
Discrete geometry on colored point sets in the plane -- a survey
On the Complexity of Nash Equilibria in Anonymous Games
Market equilibrium under separable, piecewise-linear, concave utilities
On the Complexity of Nash Equilibria and Other Fixed Points
Discrete Splittings of the Necklace
Settling the complexity of computing two-player Nash equilibria
Inapproximability of Nash Equilibrium
The Borsuk-Ulam Theorem and Bisection of Necklaces
Bisecting measures with hyperplane arrangements
A survey of mass partitions
Ham-Sandwich Cuts and Center Transversals in Subspaces
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
The Complexity of Computing a Nash Equilibrium
The complexity of splitting necklaces and bisecting ham sandwiches
Consensus halving is PPA-complete
Constant rank bimatrix games are PPAD-hard
The complexity of non-monotone markets
A Moment Problem in L 1 Approximation
Algorithms and Computation
Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: