Cut problems in graphs with a budget constraint

DOI10.1016/j.jda.2006.05.002zbMath1135.90419OpenAlexW2037387767MaRDI QIDQ2457298

Jochen Könemann, Roee Engelberg, Joseph (Seffi) Naor, Stefano Leonardi

Publication date: 30 October 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.05.002

zbMATH Keywords

combinatorial optimizationgraph theoryapproximation algorithmscut problemsbudget problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Connectivity (05C40) Methods of successive quadratic programming type (90C55)

Related Items (7)

Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Unbalanced graph partitioning ⋮ The bi-objective critical node detection problem ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ Strategic multiway cut and multicut games ⋮ On efficient vaccine distribution strategy to suppress pandemic using social relation

Cites Work

• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A note on maximizing a submodular set function subject to a knapsack constraint
• An improved approximation algorithm of MULTIWAY CUT.
• The budgeted maximum coverage problem
• A probabilistic analysis of the maximal covering location problem
• The geometry of graphs and some of its algorithmic applications
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Euclidean distortion and the sparsest cut
• Multi-Terminal Network Flows
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Increasing the Weight of Minimum Spanning Trees
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms – ESA 2005
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Cut problems in graphs with a budget constraint