Zobrazeno 1 - 10
of 1 577
pro vyhledávání: '"Zenklusen, A."'
We give a poly-time algorithm for the $k$-edge-connected spanning subgraph ($k$-ECSS) problem that returns a solution of cost no greater than the cheapest $(k+10)$-ECSS on the same graph. Our approach enhances the iterative relaxation framework with
Externí odkaz:
http://arxiv.org/abs/2311.09941
The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives is to minimize
Externí odkaz:
http://arxiv.org/abs/2308.02651
The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an $O(1)$-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revea
Externí odkaz:
http://arxiv.org/abs/2305.05353
There has been significant work recently on integer programs (IPs) $\min\{c^\top x \colon Ax\leq b,\,x\in \mathbb{Z}^n\}$ with a constraint marix $A$ with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any co
Externí odkaz:
http://arxiv.org/abs/2302.07029
Autor:
Nägele, Martin, Zenklusen, Rico
Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined p
Externí odkaz:
http://arxiv.org/abs/2301.09340
Random order online contention resolution schemes (ROCRS) are structured online rounding algorithms with numerous applications and links to other well-known online selection problems, like the matroid secretary conjecture. We are interested in ROCRS
Externí odkaz:
http://arxiv.org/abs/2211.15146
Recent progress on robust clustering led to constant-factor approximations for Robust Matroid Center. After a first combinatorial $7$-approximation that is based on a matroid intersection approach, two tight LP-based $3$-approximations were discovere
Externí odkaz:
http://arxiv.org/abs/2211.03601
Autor:
Traub, Vera, Zenklusen, Rico
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural $2$-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation f
Externí odkaz:
http://arxiv.org/abs/2209.07860
Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. This is a natural generalization of the robust (or outlier) se
Externí odkaz:
http://arxiv.org/abs/2207.02609
The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximati
Externí odkaz:
http://arxiv.org/abs/2204.06944