Degree bounded matroids and submodular flows
From MaRDI portal
Publication:2448960
DOI10.1007/s00493-012-2760-6zbMath1299.90432OpenAlexW2109095726MaRDI QIDQ2448960
Mohit Singh, Tamás Király, Lap Chi Lau
Publication date: 5 May 2014
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: http://real.mtak.hu/19505/1/kiraly_lau_singh_final.pdf
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (8)
Assignment problems with complementarities ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Stochastic packing integer programs with few queries ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
Cites Work
- 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
- Testing membership in matroid polyhedra
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Degree Bounded Forest Covering
- Survivable network design with degree or order constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Additive Guarantees for Degree-Bounded Directed Network Design
- An Algorithm for Submodular Functions on Graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
This page was built for publication: Degree bounded matroids and submodular flows
