Skip to main content
SpringerLink
Log in

An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given a positive integer k and a complete graph with non-negative edge weights satisfying the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this paper, we use the technique of factor-revealing linear programs to show that the greedy algorithm actually achieves an approximation ratio of 2, which is tight.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Baur, C., Fekete, S.P.: Approximation of geometric dispersion problems. Algorithmica 30(3), 451–470 (2001)

    MATH  MathSciNet  Google Scholar 

  2. Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI ’99: Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, Berkeley, CA, USA, pp. 173–186. USENIX Association (1999)

  3. Chandra, B., Halldórsson, M.M.: Approximation algorithms for dispersion problems. J. Algorithms 38(2), 438–465 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Czygrinow, A.: Maximum dispersion problem in dense graphs. Oper. Res. Lett. 27(5), 223–227 (2000)

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  6. Fekete, S.P., Meijer, H.: Maximum dispersion and geometric maximum weight cliques. Algorithmica 38(3), 501–511 (2003)

    Article  MathSciNet  Google Scholar 

  7. Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Math. Program. 82, 111–124 (1998)

    MathSciNet  Google Scholar 

  8. Halldórsson, M.M., Iwano, K., Katoh, N., Tokuyama, T.: Finding subsets maximizing minimum structures. SIAM J. Discrete Math. 12(3), 342–359 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  9. Hamming, R.W.: Error detecting and error correcting codes. Bell Syst. Tech. J. 26(2), 147–160 (1950)

    MathSciNet  Google Scholar 

  10. Hassin, R., Rubinstein, S., Tamir, A.: Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21(3), 133–137 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  11. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795–824 (2003)

    Article  MathSciNet  Google Scholar 

  12. Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC ’02: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 731–740. ACM Press, New York (2002)

    Chapter  Google Scholar 

  13. Kuby, M.J.: Programming models for facility dispersion: the p-dispersion and maxisum dispersion problems. Geograph. Anal. 19(4), 315–329 (1987)

    Article  Google Scholar 

  14. Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: A greedy facility location algorithm analyzed using dual fitting. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM-APPROX, Lecture Notes in Computer Science, vol. 2129, pp. 127–137. Springer, New York (2001)

    Google Scholar 

  15. McEliese, R.J., Rodemich, E.R., Rumsey, H. Jr., Welch, L.R.: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Inf. Theory 23(2), 157–166 (1977)

    Article  Google Scholar 

  16. Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized on-line matching. In: FOCS ’05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 264–273. IEEE Computer Society, Los Alamitos (2005)

    Chapter  Google Scholar 

  17. Ravi, S.S., Rosencrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2), 299–310 (1994)

    Article  MATH  Google Scholar 

  18. Rosenkrantz, D.J., Tayi, G.K., Ravi, S.S.: Facility dispersion problems under capacity and cost constraints. J. Comb. Optim. 4(1), 7–33 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  19. Rosenkrantz, D.J., Tayi, G.K., Ravi, S.S.: Obtaining online approximation algorithms for facility dispersion from offline algorithms. Networks 47(4), 206–217 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  20. Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discrete Math. 4(4), 550–567 (1991)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA, 98105-2350, USA

    Benjamin Birnbaum

  2. Department of Computer Science and Engineering, Washington University in St. Louis, Campus Box 1045, One Brookings Drive, St. Louis, MO, 63130-4899, USA

    Kenneth J. Goldman

Authors
  1. Benjamin Birnbaum
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kenneth J. Goldman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Birnbaum.

Additional information

This research was supported in part by the National Science Foundation under grant CISE-EI-0305954 and was performed while the first author was at Washington University in St. Louis. A preliminary version of this paper appears in RANDOM-APPROX ’06, volume 4110 of Lecture Notes in Computer Science, pp. 49–60, 2006.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Birnbaum, B., Goldman, K.J. An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs. Algorithmica 55, 42–59 (2009). https://doi.org/10.1007/s00453-007-9142-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9142-2

Keywords

Search

Navigation