Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs

DOI10.1007/s10878-015-9868-8zbMath1354.90102OpenAlexW1978027652MaRDI QIDQ328705

Sumit Singh, Pawan Aurora, Shashank K. Mehta

Publication date: 20 October 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9868-8

zbMATH Keywords

Lagrangian relaxationapproximation algorithmedge-packing problemsiterative rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• A unified approach to approximating partial covering problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Partial Degree Bounded Edge Packing Problem
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Improving Integrality Gaps via Chvátal-Gomory Rounding
• Two Bounds for the Domination Number of a Graph
• The constrained minimum spanning tree problem
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs