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

DOI10.1007/S10878-015-9868-8zbMATH Open1354.90102OpenAlexW1978027652MaRDI QIDQ328705FDOQ328705

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

approximation algorithmLagrangian relaxationedge-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

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The constrained minimum spanning tree 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
• Improving Integrality Gaps via Chvátal-Gomory Rounding
• Two Bounds for the Domination Number of a Graph
• SOFSEM 2006: Theory and Practice of Computer Science
• A unified approach to approximating partial covering problems
• A factor 2 approximation algorithm for the generalized Steiner network problem

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

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