Cut problems in graphs with a budget constraint

Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM Journal on Computing, 23, 864, 10.1137/S0097539792225297 Călinescu, 2000, An improved approximation algorithm for MULTIWAY CUT, Journal of Computer and Systems Sciences, 60, 564, 10.1006/jcss.1999.1687 Karger, 1999, Rounding algorithms for a geometric embedding of minimum multiway cut, 668 Aura, 2000, Analyzing single-server network inhibition, 108 Frederickson, 1999, Increasing the weight of minimum spanning trees, Journal of Algorithms, 33, 244, 10.1006/jagm.1999.1026 Arora, 2004, Expander flows, geometric embeddings and graph partitioning, 222 Aumann, 1998, An O(logk) approximate min-cut max-flow theorem and approximation algorithm, SIAM Journal on Computing, 27, 291, 10.1137/S0097539794285983 Linial, 1995, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 215, 10.1007/BF01200757 S. Chawla, A. Gupta, H. Räcke, Approximations for generalized sparsest cut and embeddings of L2 into L1, in: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), 2005 Arora, 2005, Euclidean distortion and the sparsest cut, 553 Khuller, 1999, The budgeted maximum coverage problem, Information Processing Letters, 70, 39, 10.1016/S0020-0190(99)00031-9 Räcke, 2002, Minimizing congestion in general networks, 43 Harrelson, 2003, A polynomial-time tree decomposition to minimize congestion, 34 Gomory, 1961, Multi-terminal network flows, Journal of the SIAM, 9, 551 Saran, 1995, Finding k-cuts within twice the optimal, SIAM Journal on Computing, 24, 101, 10.1137/S0097539792251730 Jain, 2001, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48, 274, 10.1145/375827.375845 Naor, 2003, Real-time scheduling with a budget, vol. 2719, 1123 Vohra, 1993, A probabilistic analysis of the maximal covering location problem, Discrete Applied Mathematics, 43, 175, 10.1016/0166-218X(93)90006-A Wolsey, 1982, Maximizing real-valued submodular functions: Primal and dual heuristics for location problems, Mathematics of Operations Research, 7, 410, 10.1287/moor.7.3.410 Sviridenko, 2004, A note on maximizing a submodular set function subject to a knapsack constraint, Operations Research Letters, 32, 41, 10.1016/S0167-6377(03)00062-2 Hayrapetyan, 2005, Unbalanced graph cuts, vol. 3669, 191 Svitkina, 2004, Min-max multiway cut, vol. 3122, 207 Ibarra, 1975, Fast approximation algorithms for the knapsack and sum of subset problems, Journal of the ACM, 22, 463, 10.1145/321906.321909 Lin, 1992, ε-approximations with minimum packing constraint violation (extended abstract), 771 Garg, 1997, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3, 10.1007/BF02523685 Vazirani, 2001