Niklas Dahlmeier, Paul Paschmanns, Laura Ritter, Ruben Skorupinski
原文摘要
We study budgeted capacity augmentation for single-source single-sink \NFOTs under constant inflow $u_0$. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel networks and provide an exact pseudopolynomial algorithm as well as a fully polynomial algorithm that attains the optimum travel time for budget $B$ while spending at most $B + \varepsilon\cdot\max\{B,u_0\}$. On general networks the problem becomes strongly NP-hard. Moreover, unless $\text{P} = \text{NP}$, for every fixed $\varepsilon \in (0,1)$, no polynomial-time algorithm can achieve the optimal steady-state travel time while exceeding the budget by at most a factor of $n^{1-\varepsilon}$. Lastly, we give structural properties about steady-state travel time under varying arc capacities. We identify capacity thresholds determined by subsets of $s$-$t$-cuts and show that the travel time is constant in the interior of the cells resulting from the corresponding hyperplane arrangement.
Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo, Ruben Skorupinski
原文摘要
We investigate the convex-body containment problem $\max\{s >0 : s Z \subseteq Q\}$, where the outer body $Q \subseteq \mathbb{R}^d$ is described by a membership oracle and the inner body $Z \subseteq \mathbb{R}^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d/\log d})$-approximation algorithm for this problem that matches the lower bound of $Ω(\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Starting from approximate Lewis position, the algorithm samples Gaussian directions and adaptively shortens and repositions the generators. Its analysis combines preservation of the support in a fixed direction with contraction of the corresponding functional after renormalization. Crucially, the algorithm works directly with the input generators and does not use zonotope sparsification. We complement this result with a \emph{universal} $Ω(\sqrt{d/\log d})$ lower bound holding for \emph{all} full-dimensional zonotopes when the number of oracle queries is polynomial in $d$. Finally, we consider containment problems $\max\{s >0 : s K \subseteq Q\}$, for general convex bodies $K \subseteq \mathbb{R}^d$. A result of Nasz{ó}di on approximating $K \subseteq \mathbb{R}^d$ by a polytope implies a $Θ(d/\log d)$ approximation algorithm in polynomial time when the centroid of $K$ is the origin. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.