2 papers
cs.GT2023
PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problem…
cs.GT2021
Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem
Eleni Batziou, Kristoffer Arnsfelt Hansen, Kasper Høgh
In the consensus halving problem we are given n agents with valuations over the interval . The goal is to divide the interval into at most pieces (by placing at most n…