On generalizations of network design problems with degree bounds

DOI10.1007/s10107-012-0537-8zbMath1295.90059arXiv1003.2977OpenAlexW2174409790MaRDI QIDQ378106

Viswanath Nagarajan, Jochen Könemann, Rohit Khandekar, Britta Peis, Nikhil Bansal

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1003.2977

zbMATH Keywords

degree boundapproximation algorithmanalysis of algorithmsspanning treenetwork designnetwork modelmatroid intersectiongraphic algorithmslattice polyhedron

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (14)

Heuristics for the network design problem with connectivity requirements ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ k-Trails: Recognition, Complexity, and Approximations ⋮ Approximation-Friendly Discrepancy Rounding ⋮ On generalizations of network design problems with degree bounds ⋮ A Spectral Approach to Network Design ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Chain-constrained spanning trees ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Degree bounded matroids and submodular flows ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generalizations of network design problems with degree bounds
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Increasing the rooted connectivity of a digraph by one
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A constant-factor approximation algorithm for the \(k\)-median problem
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• A Primal-Dual Algorithm for Weighted Abstract Cut Packing
• Lattices and Maximum Flow Algorithms in Planar Graphs
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems
• Degree Bounded Matroids and Submodular Flows
• Approximating Directed Weighted-Degree Constrained Networks
• Approximating minimum bounded degree spanning trees to within one of optimal
• Survivable Network Design with Degree or Order Constraints
• Additive Guarantees for Degree-Bounded Directed Network Design
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Iterative Rounding for Multi-Objective Optimization Problems
• A Parallel Repetition Theorem
• Local Search Heuristics for k-Median and Facility Location Problems
• Many birds with one stone
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: On generalizations of network design problems with degree bounds