Mark Velednitsky

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2018

Solving $(k - 1)$ -Stable Instances of k-Terminal Cut with Isolating Cuts

Mark Velednitsky

The k-Terminal Cut problem, also known as the Multiway Cut problem, is defined on an edge-weighted graph with $k$ distinct vertices called "terminals." The goal is to remove a mini…

cs.DS2018

DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

Minjun Chang, Dorit S. Hochbaum, Quico Spaen +1

This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a kn…

Solving (k−1)-Stable Instances of k-Terminal Cut with Isolating Cuts

DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

Solving $(k - 1)$ -Stable Instances of k-Terminal Cut with Isolating Cuts