• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Packing Multiway Cuts in Capacitated Graphs

    Thumbnail
    File(s)
    TR1642.pdf (298.6Kb)
    Date
    2008
    Author
    Chawla, Shuchi
    Barman, Siddharth
    Publisher
    University of Wisconsin-Madison Department of Computer Sciences
    Metadata
    Show full item record
    Abstract
    We consider the following ?multiway cut packing? problem in undirected graphs: we are given a graph G = (V,E) and k commodities, each corresponding to a set of terminals located at different vertices in the graph; our goal is to produce a collection of cuts {C1, ? ? ? ,Ck} such that Ci is a multiway cut for commodity i and the maximum load on any edge is minimized. The load on an edge is defined to be the number of cuts in the solution crossing the edge. In the capacitated version of the problem edges have capacities ce and the goal is to minimize the maximum relative load on any edge ? the ratio of the edge?s load to its capacity. We present constant factor approximations for this problem in arbitrary undirected graphs. The multiway cut packing problem arises in the context of graph labeling problems where we are given a partial labeling of a set of items and a neighborhood structure over them, and, informally stated, the goal is to complete the labeling in the most consistent way. This problem was introduced by Rabani, Schulman, and Swamy (SODA?08), who developed an O(log n/ log log n)approximation for it in general graphs, as well as an improved O(log2 k) approximation in trees. Here n is the number of nodes in the graph. We present an LP-based algorithm for the multiway cut packing problem in general graphs that guarantees a maximum edge load of at most 8OPT + 4. Our rounding approach is based on the observation that every instance of the problem admits a laminar solution (that is, no pair of cuts in the solution crosses) that is near-optimal. For the special case where each commodity has only two terminals and all commodities share a common sink (the ?common sink s-t cut packing? problem) we guarantee a maximum load of OPT + 1. Both of these variants are NP-hard; for the common-sink case our result is optimal.
    Permanent Link
    http://digital.library.wisc.edu/1793/60648
    Citation
    TR1642
    Part of
    • CS Technical Reports

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback