46 citations · 166 across the 16 of their papers we have counts for
3 papers · 1 filter
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…
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…
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…