4 papers
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…
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…
(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…