Chekuri, Chandra ; Gupta, Anupam ; Kumar, Amit (2005) On a bidirected relaxation for the MULTIWAY CUT problem Discrete Applied Mathematics, 150 (1-3). pp. 67-79. ISSN 0166-218X
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.dam.2005.04.003
Related URL: http://dx.doi.org/10.1016/j.dam.2005.04.003
Abstract
In the MULTIWAY CUT problem, we are given an undirected edge- weighted graph G = (V,E) with "C sub e" denoting the cost (weight) of edge e. We are also given a subset S of V, of size k, called the terminals. The objective is to find a minimum cost set of edges whose removal ensures that the terminals are disconnected. In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [10], and show that the integrality gap of this relaxation is no better than that for a geometric linear programming relaxation given by Calinescu et al [2], and may be strictly worse on some instances.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123549 |
| Deposited On: | 30 Sep 2021 10:22 |
| Last Modified: | 30 Sep 2021 10:22 |
Repository Staff Only: item control page
