Top

Published in:

2017 | OriginalPaper | Chapter

Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach

Authors : Eric Angel, Nguyen Kim Thang, Shikha Singh

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we study the k-forest problem in the model of resource augmentation. In the k-forest problem, given an edge-weighted graph G(V, E), a parameter k, and a set of m demand pairs \(\subseteq V \times V\), the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate—the best-known approximation ratio is \(O(\min \{\sqrt{n}, \sqrt{k}\})\). Furthermore, k-forest is as hard to approximate as the notoriously-hard densest k-subgraph problem.

While the k-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor.

First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k-forest problem can be viewed as to remove at most \(m-k\) demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way.

Specifically, we present a polynomial-time algorithm for the k-forest problem that, for every \(\varepsilon >0\), removes at most \(m-k\) demands and has cost no more than \(O(1/\varepsilon ^{2})\) times the cost of an optimal algorithm that removes at most \((1-\varepsilon )(m-k)\) demands.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals

next chapter Parameterized Approximation Algorithms for Some Location Problems in Graphs

Available only for authorised users

Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proceedings of the 23rd Symposium on Discrete Algorithms, pp. 1228–1241 (2012)

Angelopoulos, S., Lucarelli, G., Thang, N.K.: Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems. In: Proceedings of the 23rd European Symposium on Algorithms, pp. 35–46 (2015)

Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 136–148. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61422-2_127 CrossRef

Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an \({O}(n^{1/4})\) approximation for densest k-subgraph. In: Proceedings of the 42nd Symposium on Theory of Computing, pp. 201–210 (2010)

Birnbaum, B., Goldman, K.J.: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 55(1), 42–59 (2009)CrossRefMATHMathSciNet

Blum, A.: New approximation algorithms for graph coloring. J. ACM 41(3), 470–516 (1994)CrossRefMATHMathSciNet

Blum, A., Karger, D.: An õ (n314)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett. 61(1), 49–53 (1997)CrossRefMATH

Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244–258 (1995)CrossRefMATHMathSciNet

Charikar, M., Raghavachari, B.: The finite capacity dial-a-ride problem. In: Proceedings of the 39th Symposium on Foundations of Computer Science, pp. 458–467 (1998)

10.

Choudhury, A.R., Das, S., Garg, N., Kumar, A.: Rejecting jobs to minimize load and maximum flow-time. In: Proceedings of the 26th Symposium on Discrete Algorithms, pp. 1114–1133 (2015)

11.

Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-msts and k-steiner trees via the primal-dual method and lagrangean relaxation. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pp. 60–70 (2001)

12.

Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 228–239. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78773-0_20 CrossRef

13.

Daniely, A., Linial, N., Saks, M.: Clustering is difficult only when it does not matter. arXiv preprint arXiv:1205.4891 (2012)

14.

Devanur, N.R., Huang, Z.: Primal dual gives almost optimal energy efficient online algorithms. In: Proceedings of the 25th Symposium on Discrete Algorithms (2014)

15.

Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, pp. 427–438 (2009)

16.

Feige, U.: A threshold of ln n for approximating set cover (preliminary version). In: Proceedings of the 28th Symposium on Theory of Computing, pp. 314–318 (1996)

17.

Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174–211 (2001)CrossRefMATHMathSciNet

18.

Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)CrossRefMATHMathSciNet

19.

Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: Proceedings of the 17th Symposium on Foundations of Computer Science, pp. 216–227 (1976)

20.

Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of the 37th Symposium on Foundations of Computer Science, pp. 302–309 (1996)

21.

Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296–317 (1995)CrossRefMATHMathSciNet

22.

Gupta, A., Hajiaghayi, M., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. ACM Trans. Algorithm 6(2), 41 (2010)MATHMathSciNetCrossRef

23.

Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)CrossRefMATHMathSciNet

24.

Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Symposium on Discrete Algorithm, pp. 631–640 (2006)

25.

Im, S., Kulkarni, J., Munagala, K.: Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In: Proceedings of the 46th Symposium on Theory of Computing (2014)

26.

Im, S., Kulkarni, J., Munagala, K.: Competitive flow time algorithms for polyhedral scheduling. In: Proceedings of the 56th Symposium on Foundations of Computer Science, pp. 506–524 (2015)

27.

Im, S., Kulkarni, J., Munagala, K., Pruhs, K.: Selfishmigrate: a scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In: Proceedings of the 55th Symposium on Foundations of Computer Science (2014)

28.

Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21(1), 39–60 (2001)CrossRefMATHMathSciNet

29.

Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274–296 (2001)CrossRefMATHMathSciNet

30.

Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)CrossRefMATHMathSciNet

31.

Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000)CrossRefMATHMathSciNet

32.

Kalyanasundaram, B., Pruhs, K.R.: The online transportation problem. In: Spirakis, P. (ed.) ESA 1995. LNCS, vol. 979, pp. 484–493. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60313-1_165 CrossRef

33.

Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006)CrossRefMATHMathSciNet

34.

Klein, P.N., Young, N.E.: Approximation Algorithms for NP-Hard Optimization Problems. Chapman & Hall, Boca Raton (2010)

35.

Könemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489–509 (2011)CrossRefMATHMathSciNet

36.

Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300–317 (2000)CrossRefMATHMathSciNet

37.

Lucarelli, G., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling in a resource augmentation model based on duality. In: Proceedings of the 24th European Symposium on Algorithms (2016)

38.

Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)CrossRefMATHMathSciNet

39.

Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|V|} |{E}|)\) algorithm for finding maximum matching in general graphs. In: Proceedigs of the 21st Symposium on Foundations of Computer Science, pp. 17–27 (1980)

40.

Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause generation. Constraints 14(3), 357–391 (2009)CrossRefMATHMathSciNet

41.

Orlin, J.B.: Max flows in \({O}(nm)\) time, or better. In: Proceedigns of the 45th ACM Symposium on Theory of Computing, pp. 765–774. ACM (2013)

42.

Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163–200 (2002)CrossRefMATHMathSciNet

43.

Segev, D., Segev, G.: Approximate k-steiner forests via the lagrangian relaxation technique with internal preprocessing. Algorithmica 56(4), 529–549 (2010)CrossRefMATHMathSciNet

44.

Srivastav, A., Wolf, K.: Finding dense subgraphs with semidefinite programming. In: Jansen, K., Rolim, J. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 181–191. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0053974 CrossRef

45.

Thang, N.K.: Lagrangian duality in online scheduling with resource augmentation and speed scaling. In: Proceedigns of the 21st European Symposium on Algorithms, pp. 755–766 (2013)

46.

Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. In: 1989 30th Annual Symposium on Foundations of Computer Science, pp. 338–343. IEEE (1989)

47.

Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2013)

48.

Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J. ACM 30(4), 729–735 (1983)CrossRefMATHMathSciNet

49.

Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)CrossRefMATH

50.

Young, N.E.: On-line paging against adversarially biased random inputs. J. Algorithms 37(1), 218–235 (2000)CrossRefMATHMathSciNet

Title: Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
Authors: Eric Angel
Nguyen Kim Thang
Shikha Singh
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71147-8_23

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner