12 citations · 12 across the 4 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.DS2014
A lazy approach to on-line bipartite matching
Jakub Kozik, Grzegorz Matecki
We present a new approach, called a lazy matching, to the problem of on-line matching on bipartite graphs. Imagine that one side of a graph is given and the vertices of the other s…
cs.DS2014
An easy subexponential bound for online chain partitioning
Bartłomiej Bosek, Hal A. Kierstead, Tomasz Krawczyk +2
Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width into chains. We improve this to with a simpler and…
math.CO2014
On the Duality of Semiantichains and Unichain Coverings
Bartłomiej Bosek, Stefan Felsner, Kolja Knauer +1
We study a min-max relation conjectured by Saks and West: For any two posets and the size of a maximum semiantichain and the size of a minimum unichain covering in the prod…