• Login
    View Item 
    •   IIMA Institutional Repository Home
    • Video Library
    • R & P Seminar
    • View Item
    •   IIMA Institutional Repository Home
    • Video Library
    • R & P Seminar
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Design of survivable telecommunication network: a polyhedral approach

    Thumbnail
    View/Open
    Design of survivable telecommunication network: a polyhedral approach (129.6Mb)
    Date
    2012-09-21
    Author
    Agarwal, Yogesh K.
    Metadata
    Show full item record
    Abstract
    We consider the problem of designing a survivable telecommunication network using facilities of a fixed capacity. Given a graph G = (V, E), the traffic demand among the nodes, and the cost of installing facilities on the edges of G, we wish to design the minimum cost network, so that under any single edge failure, the network permits the flow of all traffic using the remaining capacity. The problem is modeled as a mixed integer program, which can be converted into a pure integer program by applying the well-known Japanese Theorem on multi-commodity flows. Using a key theorem that characterizes the facet inequalities of this integer program, we derive several families of 3- and 4-partition facets, which help to achieve extremely tight lower bounds on the problem. Using these bounds, problems of up to 20 nodes and 40 edges have been solved optimally in a pervious work. Using heuristic approaches based on this framework, we solve problems of up to 40 nodes and 80 edges to obtain solutions that are approximately within 5% of optimal solutions.
    URI
    http://hdl.handle.net/11718/11862
    Collections
    • R & P Seminar [209]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of IIMA Institutional RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV