2 citations · 2 across the 4 of their papers we have counts for
8 papers
On the cost of essentially fair clusterings
Ioana O. Bercea, Martin Groß, Samir Khuller +4
Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this proc…
On the Complexity of Instationary Gas Flows
Martin Groß, Marc E. Pfetsch, Martin Skutella
We study a simplistic model of instationary gas flows consisting of a sequence of k stationary gas flows. We present efficiently solvable cases and NP-hardness results, establishin…
A Local-Search Algorithm for Steiner Forest
Martin Groß, Anupam Gupta, Amit Kumar +4
In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connec…
General Bounds for Incremental Maximization
Aaron Bernstein, Yann Disser, Martin Groß
We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardi…
A -Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts
Samuel Fiorini, Martin Groß, Jochen Könemann +1
The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree , an additional set of edges called links and…
Scheduling Maintenance Jobs in Networks
Fidaa Abed, Lin Chen, Yann Disser +5
We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focu…
Graph Orientation and Flows Over Time
Ashwin Arulselvan, Martin Groß, Martin Skutella
Flows over time are used to model many real-world logistic and routing problems. The networks underlying such problems -- streets, tracks, etc. -- are inherently undirected and dir…
A tight bound on the speed-up through storage for quickest multi-commodity flows
Martin Groß, Martin Skutella
Multi-commodity flows over time exhibit the non-intuitive property that letting flow wait can allow us to send flow faster overall. Fleischer and Skutella (IPCO~2002) show that the…