13 citations · 26 across the 17 of their papers we have counts for
9 papers · 1 filter
A Note on the Quickest Minimum Cost Transshipment Problem
Martin Skutella
Klinz and Woeginger (1995) prove that the minimum cost quickest flow problem is NP-hard. On the other hand, the quickest minimum cost flow problem can be solved efficiently via a s…
Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
Sven Jäger, Martin Skutella
Minimizing the sum of weighted completion times on identical parallel machines is one of the most important and classical scheduling problems. For the stochastic variant where…
Robust randomized matchings
Jannik Matuschke, Martin Skutella, José A. Soto
The following game is played on a weighted graph: Alice selects a matching and Bob selects a number . Alice's payoff is the ratio of the weight of the heaviest edges of…
A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective
Martin Skutella
We present a -approximation algorithm for the nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on a single machine sub…
Protection of flows under targeted attacks
Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo +2
Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. We concentrate on…
Node-balancing by edge-increments
Friedrich Eisenbrand, Shay Moran, Rom Pinchasi +1
Suppose you are given a graph with a weight assignment and that your objective is to modify using legal steps such that all vertices will h…