Algorithms for a network design problem with crossing supermodular demands

DOI10.1002/net.20005zbMath1053.90013OpenAlexW2012586162MaRDI QIDQ4474300

Éva Tardos, Vardges Melkonian

Publication date: 4 August 2004

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20005

zbMATH Keywords

linear programmingapproximation algorithmsbasic solutionsnetwork design problemscrossing supermodular functions

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items (7)

LP-based solution methods for the asymmetric TSP ⋮ Approximation Algorithms for Multi-budgeted Network Design Problems ⋮ On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs ⋮ Approximating directed weighted-degree constrained networks ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ The \(k\)-path tree matroid and its applications to survivable network design ⋮ Approximating the smallest k -edge connected spanning subgraph by LP-rounding

Cites Work

• Geometric algorithms and combinatorial optimization
• Biconnectivity approximations and graph carvings
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms for a network design problem with crossing supermodular demands