## 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^{2}), 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 | |

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 |

## Scopus Subject Areas

- Electrical and Electronic Engineering