On the L_-norm of extreme points for crossing supermodular directed network LPs

DOI10.1007/S10107-006-0061-9zbMATH Open1111.90115OpenAlexW2110257828MaRDI QIDQ877196FDOQ877196

Authors: Harold N. Gabow 

Publication date: 19 April 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0061-9

Recommendations

• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Algorithms for a network design problem with crossing supermodular demands
• scientific article; zbMATH DE number 1342141
• Directed Network Design with Orientation Constraints
• Additive guarantees for degree-bounded directed network design

zbMATH Keywords

Approximation algorithmsLinear programmingNetwork designBasic feasible solutionCrossing supermodular functionDirected networksExtreme pointIterated rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Biconnectivity approximations and graph carvings
• Title not available (Why is that?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
• Approximation algorithms for minimum-cost k-vertex connected subgraphs
• Approximation Algorithms for Several Graph Augmentation Problems
• Algorithms for a network design problem with crossing supermodular demands
• Submodular functions in graph theory
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Title not available (Why is that?)

Cited In (2)

• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding

This page was built for publication: On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877196)