28 citations · 62 across the 18 of their papers we have counts for
4 papers · 1 filter
A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
Stephan Beyer, Markus Chimani, Joachim Spoerhase
We propose a simple and natural approximation algorithm for the problem of finding a 2-edge-connected spanning subgraph of minimum total edge cost in a graph. The algorithm maintai…
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity
Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar +2
We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizon…
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase +1
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixe…
Approximating Node-Weighted k-MST on Planar Graphs
Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
We study the problem of finding a minimum weight connected subgraph spanning at least vertices on planar, node-weighted graphs. We give a $(4+\eps)$-approximation algorithm for…