46 citations · 166 across the 16 of their papers we have counts for
6 papers · 1 filter
Improved Approximation Algorithms for Relay Placement
Alon Efrat, Sándor P. Fekete, Joseph S. B. Mitchell +2
In the relay placement problem the input is a set of sensors and a number , the communication range of a relay. In the one-tier version of the problem the objective is to…
On Minimizing Crossings in Storyline Visualizations
Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk +2
In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by -monotone curves that converge for each interaction, and dive…
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…
Almost stable matchings in constant time
Patrik Floréen, Petteri Kaski, Valentin Polishchuk +1
We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose--accept rounds executed by the Gale--Shapley algorithm for the stable marr…
The Minimum Backlog Problem
Michael A. Bender, Sándor P. Fekete, Alexander Kröller +4
We study the minimum backlog problem (MBP). This online problem arises, e.g., in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-perso…
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…