5 papers
Continuous Computational Social Choice: A Case Study in Bribery
Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu +1
Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly mode…
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
Christoph Hunkenschröder, Martin Koutecký, Asaf Levin +1
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mat…
Solving Multiagent Path Finding on Highly Centralized Networks
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +3
The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destin…
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
Generalized -Center: Distinguishing Doubling and Highway Dimension
Andreas Emil Feldmann, Tung Anh Vu
We consider generalizations of the -Center problem in graphs of low doubling and highway dimension. For the Capacitated -Supplier with Outliers (CkSwO) problem, we show an ef…