Skip to main content
SpringerLink
Log in

Local search for Hamiltonian Path with applications to clustering visitation paths

  • Part Special Issue
  • Published:
Journal of the Operational Research Society

Abstract

Clustering a data array has been found useful in the design of web-sites and distributed database system. We show that a critical step during this clustering process is related to solving the Longest Hamiltonian Path Problem, a well known NP-complete problem. Using the grouping of visitation paths of web-users as a case study, we test several heuristic algorithms. As a result of our experiments, we identify a successful method for dealing with this problem. Our algorithm spends less CPU time and provides better quality solutions than the most recent approach.

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

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15

Similar content being viewed by others

References

  • McCormick Jr WT, Schweitzer PJ and White TW (1972). Problem decomposition and data reorganization by a clustering technique. Opns Res 20: 993–1009.

    Article  Google Scholar 

  • Chinchwadkar GS and Goh A (1999). An overview of vertical partitioning in object oriented databases. Comput J 42: 39–50.

    Article  Google Scholar 

  • Lin X, Orlowska M and Zhang Y (1993). A graph based cluster approach for vertical partitioning in database design. Data Knowl Engng 11: 151–169.

    Article  Google Scholar 

  • Özsu MT and Valduriez P (1999). Principles of Distributed Database Systems, 2nd edn. Prentice-Hall: Englewood Cliffs, NJ.

    Google Scholar 

  • Xiao J, Zhang Y, Jia X and Li T (2001). Measuring similarity of interests for clustering web-users. In: Orlowska ME and Roddick JR (eds). Australian Computer Science Communications. Database Technologies, Proceedings of the 12th Australasian Database Conference ADC 2001, Vol 23. IEEE Computer Society: Silver Spring, MD, pp 107–114.

    Google Scholar 

  • Amirahnadi F and Choobineh F (1996). Identifying the composition of a cellular manufacturing system. Int J Prod Res 34: 2471–2488.

    Article  Google Scholar 

  • Askin RG, Cresswell SH, Golberd JB and Vakharia AJ (1991). A Hamiltonian Path approach to reordering the part-machine matrix for cellular manufacturing. Int J Prod Res 29: 1081–1100.

    Article  Google Scholar 

  • Boctor FF (1996). The minimum-cost, machine-part cell formation problem. Int J Prod Res 34: 1045–1063.

    Article  Google Scholar 

  • Lozano S, Adenso-Díaz B, Eguia I and Oniseva L (1999). A one-step tabu search algorithm for manufacturing cell design. J Opl Res Soc 50: 509–516.

    Article  Google Scholar 

  • Sarker BR and Li Z (1998). Measuring matrix-based cell formation with alternative routings. J Opl Res Soc 49: 953–965.

    Article  Google Scholar 

  • Hochbaum DS (ed) (1997). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company: Boston, MA.

    Google Scholar 

  • Perkowitz M and Etzioni O (1998). Adaptive web sites: Automatically synthesizing web pages. In: Proceedings of the 15th National Conference on Artificial Intelligence, Madison, WI, July 1998 American Association for Artificial Intelligence. AAAI Press, pp 727–732.

  • Doyle J (1994). Clumping data in 2-way tables: a user-oriented perspective. J Opl Res Soc 45: 203–213.

    Article  Google Scholar 

  • Harhalakis G, Lu T, Minis I and Nagi R (1996). A practical method for design of hybrid-type production facilities. Int J Prod Res 34: 897–918.

    Article  Google Scholar 

  • Cheng C-H (1995). A branch and bound clustering algorithm. IEEE Trans Systems Man Cybern 25: 895–898.

    Article  Google Scholar 

  • Veeramani D and Mani K (1996). A polynomial-time algorithm for optimal clustering in a special class of 0,1-matrices. Int J Prod Res 34: 2587–2611.

    Article  Google Scholar 

  • Ng SM (1991). Bond energy, rectilinear distance and a worst-case bound for the group technology problem. J Opl Res Soc 42: 571–578.

    Article  Google Scholar 

  • Aarts E and Lenstra JK (1997). Introduction. In: Aarts E and Lenstra JK (eds) Local Search in Combinatorial Optimization. John Wiley & Sons, New York, pp 1–17.

    Google Scholar 

  • Croes GA (1958). A method for solving traveling-salesman problems. Opns Res 5: 791–812.

    Article  Google Scholar 

  • Garey MR and Johnson DS (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. WH Freeman and Company: New York.

    Google Scholar 

  • Garfinkel RS (1985). Motivation and modelling. In: Lawler EL, Lenstra JK, Rinnooy Kan AHG and Shmoys DB (eds). The Traveling Salesman Problem. John Wiley & Sons, New York, pp 17–36.

    Google Scholar 

  • Lawler EL, Lenstra JK, Rinnooy Kan AHG and Shmoys DB (eds) (1985). The Traveling Salesman Problem. John Wiley & Sons, New York.

    Google Scholar 

  • Lenstra JK (1974). Clustering a data array and the traveling-salesman problem. Opns Res 22: 413–414.

    Article  Google Scholar 

  • Fredman ML, Johnson DS, McGeoch LA and Ostheimer G (1995). Data structures for traveling salesmen. J Algorithms 18: 432–479.

    Article  Google Scholar 

  • Lin S and Kernighan BW (1973). An effective heuristic for the traveling- salesman problem. Opns Res 21: 498–516.

    Article  Google Scholar 

  • Johnson DS and McGeoch LA (1997). The traveling salesman problem: a case study. In: E Aarts and JK Lenstra (eds). Local Search in Combinatorial Optimization. John Wiley & Sons, New York, pp 215–310.

    Google Scholar 

  • Kindervater GAP and Savelsbergh MWP (1997). Vehicle routing: handling edge exchanges. In: E Aarts and JK Lenstra (eds). Local Search in Combinatorial Optimization. John Wiley & sons, New York, pp 337, 360.

    Google Scholar 

  • Chandra B, Karloff H and Tovey C (1999). New results on the old k-opt algorithm for the traveling salesman problem. SIAM J Comput 28: 1998–2029.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. PHI Investigación Operativa para la alta Dirección de Empresas SA de CV, Av. Acoxpa 524-506A, Col. Prados Coapa, Tlalpan DF, 14390, Mexico

    R Torres-Velázquez

  2. Griffith University, Brisbane, 4111 QLD, Australia

    V Estivill-Castro

Authors
  1. R Torres-Velázquez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V Estivill-Castro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R Torres-Velázquez.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Torres-Velázquez, R., Estivill-Castro, V. Local search for Hamiltonian Path with applications to clustering visitation paths. J Oper Res Soc 55, 737–748 (2004). https://doi.org/10.1057/palgrave.jors.2601770

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2601770

Keywords

Search

Navigation