Skip to main content
Springer Nature Link
Log in

On a linearization technique for solving the quadratic set covering problem and variations

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this paper we identify various inaccuracies in the paper by Saxena and Arora (Optimization 39:33–42, 1997). In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. Experimental analysis has been carried out to assess the value of this algorithm as a heuristic. The results disclose that for some classes of problems the Saxena–Arora algorithm is effective in achieving good quality solutions while for some other classes of problems, its performance is poor. We also discuss similar inaccuracies in another related paper.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. Adams, W.P., Sherali, H.D.: A tight linearization and an algorithm for zero-one quadratic programming problems. Manag. Sci. 32, 1274–1290 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  2. Balas, E., Ho, A.: Set covering algorithms using cutting planes, heuristics, and sub-gradient optimization: a computational study. Math. Progr. 12, 37–60 (1980)

    MATH  Google Scholar 

  3. Bazaraa, M.S., Goode, J.J.: A cutting-plane algorithm for the quadratic set-covering problem. Oper. Res. 23, 150–158 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  4. Beasley, J.E.: A lagrangian heuristic for set-covering problems. Naval Res. Logist. 37, 151–164 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bector C.R., Bhatt S.K.: A linearization technique for solving integral linear fractional program: Proc. fifth Manitoba Conference on Numerical Mathematics, pp. 221–229 (1975)

  6. Custic A., Punnen A.P.: A characterization of linearizable instances of the quadratic minimum spanning tree problem. arXiv:1510.02197 (2015)

  7. Escoffier, B., Hammer, P.L.: Approximation of the quadratic set covering problem. Discrete Optim. 4, 378–386 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Garfinkel, R.S., Nemhauser, G.L.: Integer Programming. Wiley, New York (1972)

    MATH  Google Scholar 

  9. Grossman, T., Wool, A.: Computational experience with approximation algorithms for the set covering problem. Eur. J. Oper. Res. 101, 81–92 (1997)

    Article  MATH  Google Scholar 

  10. Gupta, R., Saxena, R.R.: Linearization technique for solving quadratic set packing and partitioning problems. Int. J. Math. Comput. Appl. Res. 4, 9–20 (2014)

    Google Scholar 

  11. Gupta, R., Saxena, R.R.: Set packing problem with linear fractional objective function. Int. J. Math. Comput. Appl. Res. 4, 9–18 (2014)

    Google Scholar 

  12. Kabadi, S.N., Punnen, A.P.: An \(O(n^4)\) algorithm for the QAP linearization problem. Math. Oper. Res. 36, 754–761 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Lemke, C.E., Salkin, H.M., Spielberg, K.: Set covering by single branch enumeration with linear programming sub-problem. Oper. Res. 19, 998–1022 (1971)

    Article  MATH  Google Scholar 

  14. Liberti L.: Compact linearization for binary quadratic problems. 4OR 5:231–245 (2007)

  15. Periannan, M.: An ant-based algotithm for the minimum vertex cover problem: Thesis. The Pennsylvania State University, Master of Science (2007)

  16. Punnen, A.P., Kabadi, S.N.: A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discrete Optim. 10, 200–209 (2013)

    Article  MathSciNet  Google Scholar 

  17. Saxena, R.R., Arora, S.R.: A linearization technique for solving the quadratic set covering problem. Optimization 39, 33–42 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Xu, K.: http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm

Download references

Acknowledgments

This work was supported by an NSERC discovery Grant awarded to Abraham Punnen.

Author information

Authors and Affiliations

  1. Department of Mathematics, Simon Fraser University, 250-13450 102nd Avenue, Surrey, BC, V3T 0A3, Canada

    Pooja Pandey & Abraham P. Punnen

Authors
  1. Pooja Pandey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abraham P. Punnen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pooja Pandey.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pandey, P., Punnen, A.P. On a linearization technique for solving the quadratic set covering problem and variations. Optim Lett 11, 1357–1370 (2017). https://doi.org/10.1007/s11590-016-1081-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-016-1081-x

Keywords

Search

Navigation