46 citations · 166 across the 16 of their papers we have counts for
4 papers · 1 filter
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…
Geodesic diameter of a polygonal domain in O(n^4 log n) time
Mikko Koivisto, Valentin Polishchuk
We show that the geodesic diameter of a polygonal domain with n vertices can be computed in O(n^4 log n) time by considering O(n^3) candidate diameter endpoints; the endpoints are…
Simple Wriggling is Hard unless You Are a Fat Hippo
Irina Kostitsyna, Valentin Polishchuk
We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest pa…
Local algorithms in (weakly) coloured graphs
Matti Åstrand, Valentin Polishchuk, Joel Rybicki +2
A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum d…