Leonid Zosin

According to our database, Leonid Zosin authored at least 8 papers between 1996 and 2004.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin

SIAM J. Discret. Math., 2004

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.

Michael E. Saks, Alex Samorodnitsky, Leonid Zosin

Comb., 2004

2002

On directed Steiner trees.

Leonid Zosin, Samir Khuller

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

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

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

1997

Relaxed multi-commodity flow and its application to the design of approximation algorithms.

Leonid Zosin

PhD thesis, 1997

A 2-Approximation Algorithm for the Directed Multiway Cut Problem.

Joseph Naor, Leonid Zosin

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications.

Guy Even, Joseph Naor, Baruch Schieber, Leonid Zosin

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

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

Guy Even, Joseph Naor, Leonid Zosin

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996