The bi-weighted TSP problem for VLSI crosstalk minimization

D. F. Wong, Muzhou Shao

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-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(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.

Original languageEnglish
Title of host publicationProceedings - IEEE International Symposium on Circuits and Systems, ISCAS 2002
PublisherIEEE
PagesIII/767-III/770
Number of pages4
ISBN (Print)0780374487
DOIs
Publication statusPublished - May 2002
Event2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002 - Phoenix-Scottsdale, United States
Duration: 26 May 200229 May 2002
https://ieeexplore.ieee.org/xpl/conhome/7897/proceeding

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems
PublisherIEEE
ISSN (Print)0271-4310

Conference

Conference2002 IEEE International Symposium on Circuits and Systems, ISCAS 2002
Country/TerritoryUnited States
CityPhoenix-Scottsdale
Period26/05/0229/05/02
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'The bi-weighted TSP problem for VLSI crosstalk minimization'. Together they form a unique fingerprint.

Cite this