The bi-weighted TSP problem for VLSI crosstalk minimization

D. F. Wong; Muzhou Shao

doi:10.1109/ISCAS.2002.1010337

The bi-weighted TSP problem for VLSI crosstalk minimization

D. F. Wong
, Muzhou Shao

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

Abstract

We consider a special traveling salesman problem (TSP) called bi-weighted TSP. The problem of determining an optimal ordering for a set of parallel wires to minimize crosstalk noise can be formulated as a bi-weighted TSP problem. Let G be an undirected complete weighted graph where the weight (cost) on each edge is either 1 or 1 + α. The objective of the bi-weighted TSP problem is to find a minimum cost Hamiltonian path in G. Existing algorithms for general TSP (e.g., nearest-neighbor algorithm and Christofide algorithm) can be applied to solve this problem. In this paper, we prove that the nearest-neighbor algorithm has worst case performance ratio of 1 + α/2 and the bound is tight. We also show that the algorithm is asymptotically optimal when m is o(n²), where n is the number of nodes in G and m is the number of edges with cost 1 + α. Analysis of the Christofide algorithm will also be presented.

Original language	English
Title of host publication	Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002
Publisher	IEEE
Pages	III/767-III/770
Number of pages	4
ISBN (Print)	0780374487
DOIs	https://doi.org/10.1109/ISCAS.2002.1010337
Publication status	Published - May 2002
Event	2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002 - Phoenix-Scottsdale, United States Duration: 26 May 2002 → 29 May 2002 https://ieeexplore.ieee.org/xpl/conhome/7897/proceeding

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Publisher	IEEE
ISSN (Print)	0271-4310

Conference

Conference	2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002
Country/Territory	United States
City	Phoenix-Scottsdale
Period	26/05/02 → 29/05/02
Internet address	https://ieeexplore.ieee.org/xpl/conhome/7897/proceeding

Access to Document

10.1109/ISCAS.2002.1010337

Cite this

@inproceedings{7136c0703eef4f5cbf27b287a65ede00,

title = "The bi-weighted TSP problem for VLSI crosstalk minimization",

abstract = "We consider a special traveling salesman problem (TSP) called bi-weighted TSP. The problem of determining an optimal ordering for a set of parallel wires to minimize crosstalk noise can be formulated as a bi-weighted TSP problem. Let G be an undirected complete weighted graph where the weight (cost) on each edge is either 1 or 1 + α. The objective of the bi-weighted TSP problem is to find a minimum cost Hamiltonian path in G. Existing algorithms for general TSP (e.g., nearest-neighbor algorithm and Christofide algorithm) can be applied to solve this problem. In this paper, we prove that the nearest-neighbor algorithm has worst case performance ratio of 1 + α/2 and the bound is tight. We also show that the algorithm is asymptotically optimal when m is o(n2), where n is the number of nodes in G and m is the number of edges with cost 1 + α. Analysis of the Christofide algorithm will also be presented.",

author = "Wong, \{D. F.\} and Muzhou Shao",

note = "Funding Information: This work was partially supported by the National Science Foundation under grant CCR-9912390.; 2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002 ; Conference date: 26-05-2002 Through 29-05-2002",

year = "2002",

month = may,

doi = "10.1109/ISCAS.2002.1010337",

language = "English",

isbn = "0780374487",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "IEEE",

pages = "III/767--III/770",

booktitle = "Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/7897/proceeding",

}

Wong, DF & Shao, M 2002, The bi-weighted TSP problem for VLSI crosstalk minimization. in Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002. Proceedings - IEEE International Symposium on Circuits and Systems, IEEE, pp. III/767-III/770, 2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002, Phoenix-Scottsdale, Arizona, United States, 26/05/02. https://doi.org/10.1109/ISCAS.2002.1010337

The bi-weighted TSP problem for VLSI crosstalk minimization. / Wong, D. F.; Shao, Muzhou.
Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002. IEEE, 2002. p. III/767-III/770 (Proceedings - IEEE International Symposium on Circuits and Systems).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - The bi-weighted TSP problem for VLSI crosstalk minimization

AU - Wong, D. F.

AU - Shao, Muzhou

N1 - Funding Information: This work was partially supported by the National Science Foundation under grant CCR-9912390.

PY - 2002/5

Y1 - 2002/5

N2 - We consider a special traveling salesman problem (TSP) called bi-weighted TSP. The problem of determining an optimal ordering for a set of parallel wires to minimize crosstalk noise can be formulated as a bi-weighted TSP problem. Let G be an undirected complete weighted graph where the weight (cost) on each edge is either 1 or 1 + α. The objective of the bi-weighted TSP problem is to find a minimum cost Hamiltonian path in G. Existing algorithms for general TSP (e.g., nearest-neighbor algorithm and Christofide algorithm) can be applied to solve this problem. In this paper, we prove that the nearest-neighbor algorithm has worst case performance ratio of 1 + α/2 and the bound is tight. We also show that the algorithm is asymptotically optimal when m is o(n2), where n is the number of nodes in G and m is the number of edges with cost 1 + α. Analysis of the Christofide algorithm will also be presented.

AB - We consider a special traveling salesman problem (TSP) called bi-weighted TSP. The problem of determining an optimal ordering for a set of parallel wires to minimize crosstalk noise can be formulated as a bi-weighted TSP problem. Let G be an undirected complete weighted graph where the weight (cost) on each edge is either 1 or 1 + α. The objective of the bi-weighted TSP problem is to find a minimum cost Hamiltonian path in G. Existing algorithms for general TSP (e.g., nearest-neighbor algorithm and Christofide algorithm) can be applied to solve this problem. In this paper, we prove that the nearest-neighbor algorithm has worst case performance ratio of 1 + α/2 and the bound is tight. We also show that the algorithm is asymptotically optimal when m is o(n2), where n is the number of nodes in G and m is the number of edges with cost 1 + α. Analysis of the Christofide algorithm will also be presented.

UR - https://www.scopus.com/pages/publications/0036294771

U2 - 10.1109/ISCAS.2002.1010337

DO - 10.1109/ISCAS.2002.1010337

M3 - Conference proceeding

AN - SCOPUS:0036294771

SN - 0780374487

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - III/767-III/770

BT - Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002

PB - IEEE

T2 - 2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002

Y2 - 26 May 2002 through 29 May 2002

ER -

The bi-weighted TSP problem for VLSI crosstalk minimization

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this