Approximating k-cuts using network strength as a Lagrangean relaxation |
| |
| Authors: | R. Ravi Amitabh Sinha |
| |
| Affiliation: | 1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;2. Ross School of Business, University of Michigan, Ann Arbor, MI 48109, USA |
| |
| Abstract: | Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points are in different components. |
| |
| Keywords: | Combinatorial optimization Graph theory Approximation algorithm Lagrangean relaxation |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
