43 citations · 43 across the 2 of their papers we have counts for
3 papers
cs.DS2010
Improved approximations for robust mincut and shortest path
Valentin Polishchuk, Mikko Sysikaski
In two-stage robust optimization the solution to a problem is built in two stages: In the first stage a partial, not necessarily feasible, solution is exhibited. Then the adversary…
cs.DC2008★ 43 cited
A simple local 3-approximation algorithm for vertex cover
Valentin Polishchuk, Jukka Suomela
We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxilia…
cs.DS2006
The Snowblower Problem
Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell +1
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP i…