Leonid Zosin

SODA Conference 2002 Conference Paper

On directed Steiner trees

• Leonid Zosin
• Samir Khuller

SODA Conference 2001 Conference Paper

Approximation algorithms for the metric labeling problem via a new linear programming formulation

• Chandra Chekuri
• Sanjeev Khanna
• Joseph Naor
• Leonid Zosin

FOCS Conference 1997 Conference Paper

A 2-Approximation Algorithm for the Directed Multiway Cut Problem

• Joseph Naor
• Leonid Zosin

A directed multiway cut separates a set of terminals s/sub 1/, .. ., s/sub /spl kappa// in a directed capacitated graph G=(V, E). Finding a minimum capacity directed multiway cut is an NP-complete problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani and Yannakakis (1994) who gave an algorithm that achieves an approximation factor of 2 log /spl kappa/. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.

FOCS Conference 1996 Conference Paper

An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem

• Guy Even
• Joseph Naor
• Leonid Zosin

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set. The input in this problem consists of an undirected graph G=(V, E) with vertex weights w(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset feedback vertex set with respect to S if it intersects every interesting cycle The goal is to find a minimum weight subset feedback vertex set. The best pervious algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset feedback vertex set problem generalizes two NP-Complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multi-commodity flow which we call relaxed multi-commodity flow. Relaxed multi-commodity flow is a hybrid of multi-commodity flow and multi-terminal flow.