Degree bounded matroids and submodular flows

DOI10.1007/S00493-012-2760-6MaRDI QIDQ2448960zbMATH OpenOpenAlexFDO

Authors Tamás Király, Lap Chi Lau, Mohit Singh

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

zbMATH Keywords

bounded degree problemscomplexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The complexity of several rather restricted tasks is elaborated in interdependency of: minimum bounded degree matroid basis, minimum bounded degree submodular flow, minimum bounded degree spanning tree, minimum crossing spanning tree, minimum bounded-ones binary matroid basis, minimum bounded degree graph orientation, etc. There are many proofs in verbal form over 5 or 6 lines. In addition, one will find three long proofs in verbose form. All this is obviously relevant to those who are highly specialized in the field.

Recommendations

• Degree Bounded Matroids and Submodular Flows
• Approximating bounded degree deletion via matroid matching
• Approximating minimum bounded degree spanning trees to within one of optimal
• Matroidal degree-bounded minimum spanning trees

Cites work

• 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
• Additive guarantees for degree-bounded directed network design
• An Algorithm for Submodular Functions on Graphs
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Degree bounded forest covering
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• Survivable network design with degree or order constraints
• Testing membership in matroid polyhedra

Cited in

(12)

• \(k\)-trails: recognition, complexity, and approximations
• Stochastic packing integer programs with few queries
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Assignment problems with complementarities
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Approximate multi-matroid intersection via iterative refinement
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Design and topological analysis of complex networks with optimal controllability
• An optimal absolute approximation algorithm for computing k disjoint restricted shortest paths
• Approximating maximum-size properly colored forests
• Approximating maximum-size properly colored forests

This page was built for publication: Degree bounded matroids and submodular flows

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