Near-optimal heuristic algorithm for single-row routing

L. C. Liu, David H Du

Research output: Contribution to journalArticlepeer-review


The authors obtain a tighter lower bound on the street congestion of optimal realizations. Then a heuristic algorithm based on necessary and sufficient conditions of optimality is proposed. Although it cannot be guaranteed that this algorithm always generates optimal realizations, it indeed generates optimal realizations for all the 60 test instances with which they experimented. This algorithm is also shown to be time efficient.

Original languageEnglish (US)
Pages (from-to)603-608
Number of pages6
JournalIEEE Transactions on Computers
Issue numbern
StatePublished - 1992


Dive into the research topics of 'Near-optimal heuristic algorithm for single-row routing'. Together they form a unique fingerprint.

Cite this