Browsing Computer Science and Engineering by Author "Vazirani, Vijay V"
Now showing items 14 of 4

Improved bounds for the maxflow minmulticut ratio for planar and Kr, rfree graphs
Tardos, Éva; Vazirani, Vijay V (1993)We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this ... 
Multiway cuts in node weighted graphs
Garg, Naveen; Vazirani, Vijay V; Yannakakis, Mihalis (2004)A (2−2/k) approximation algorithm is presented for the node multiway cut problem, thus matching the result of Dahlhaus et al. (SIAM J. Comput. 23 (4) (1994) 864–894) for the edge version of this problem. This is done by ... 
Online algorithms for weighted bipartite matching and stable marriages
Khuller, Samir; Mitchell, Stephen G; Vazirani, Vijay V (1994)We give an online deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal  there ... 
Planar graph coloring is not selfreducible, assuming P ≠ NP
Vazirani, Vijay V; Khuller, Samir (1991)We show that obtaining the lexicographically first four coloring of a planar graph is NPhard. This shows that planar graph fourcoloring is not selfreducible, assuming P≠ NP. One consequence of our result is that the ...