A 2.5 Approximation Algorithm for the Multi-Via Assignment Problem

Thang Nguyen Bui; Willie Hsu; Sing Ling Lee

doi:10.1109/43.177396

A 2.5 Approximation Algorithm for the Multi-Via Assignment Problem

Thang Nguyen Bui, Willie Hsu, Sing Ling Lee

School of Science, Engineering & Technology (Harrisburg)

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

An important phase in the single row routing approach for multilayer printed circuit board routing is the via assignment phase. The via assignment problem, whose objective is to minimize the number of via columns used, is known to be NP-hard even when each net includes at most three vias. In this paper, we develop efficient approximation algorithms for solving this problem. When the size of each net is bounded by three, we present an algorithm which guarantees that the solution generated uses no more than 2OPT_C — 1 via columns, and no more than [(4/3)OPT_v \ vias, where OPT_cand OPT_vare the number of via columns and vias in an optimal solution. We then extend our result to the case that the nets have arbitrary sizes. An efficient algorithm is presented which guarantees the solution generated uses no more than [2.5OPT_c] via columns and no more than [1.5OPT_V] vias in the worst case.

Original language	English (US)
Pages (from-to)	1325-1333
Number of pages	9
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	11
Issue number	11
DOIs	https://doi.org/10.1109/43.177396
State	Published - Nov 1992

All Science Journal Classification (ASJC) codes

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/43.177396

Cite this

@article{8c6d6fccb7b84ba4930a76682933fb41,

title = "A 2.5 Approximation Algorithm for the Multi-Via Assignment Problem",

abstract = "An important phase in the single row routing approach for multilayer printed circuit board routing is the via assignment phase. The via assignment problem, whose objective is to minimize the number of via columns used, is known to be NP-hard even when each net includes at most three vias. In this paper, we develop efficient approximation algorithms for solving this problem. When the size of each net is bounded by three, we present an algorithm which guarantees that the solution generated uses no more than 2OPTC — 1 via columns, and no more than [(4/3)OPTv \ vias, where OPTcand OPTvare the number of via columns and vias in an optimal solution. We then extend our result to the case that the nets have arbitrary sizes. An efficient algorithm is presented which guarantees the solution generated uses no more than [2.5OPTc] via columns and no more than [1.5OPTV] vias in the worst case.",

author = "Bui, {Thang Nguyen} and Willie Hsu and Lee, {Sing Ling}",

year = "1992",

month = nov,

doi = "10.1109/43.177396",

language = "English (US)",

volume = "11",

pages = "1325--1333",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

T1 - A 2.5 Approximation Algorithm for the Multi-Via Assignment Problem

AU - Bui, Thang Nguyen

AU - Hsu, Willie

AU - Lee, Sing Ling

PY - 1992/11

Y1 - 1992/11

N2 - An important phase in the single row routing approach for multilayer printed circuit board routing is the via assignment phase. The via assignment problem, whose objective is to minimize the number of via columns used, is known to be NP-hard even when each net includes at most three vias. In this paper, we develop efficient approximation algorithms for solving this problem. When the size of each net is bounded by three, we present an algorithm which guarantees that the solution generated uses no more than 2OPTC — 1 via columns, and no more than [(4/3)OPTv \ vias, where OPTcand OPTvare the number of via columns and vias in an optimal solution. We then extend our result to the case that the nets have arbitrary sizes. An efficient algorithm is presented which guarantees the solution generated uses no more than [2.5OPTc] via columns and no more than [1.5OPTV] vias in the worst case.

AB - An important phase in the single row routing approach for multilayer printed circuit board routing is the via assignment phase. The via assignment problem, whose objective is to minimize the number of via columns used, is known to be NP-hard even when each net includes at most three vias. In this paper, we develop efficient approximation algorithms for solving this problem. When the size of each net is bounded by three, we present an algorithm which guarantees that the solution generated uses no more than 2OPTC — 1 via columns, and no more than [(4/3)OPTv \ vias, where OPTcand OPTvare the number of via columns and vias in an optimal solution. We then extend our result to the case that the nets have arbitrary sizes. An efficient algorithm is presented which guarantees the solution generated uses no more than [2.5OPTc] via columns and no more than [1.5OPTV] vias in the worst case.

UR - http://www.scopus.com/inward/record.url?scp=0026943140&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026943140&partnerID=8YFLogxK

U2 - 10.1109/43.177396

DO - 10.1109/43.177396

M3 - Article

AN - SCOPUS:0026943140

SN - 0278-0070

VL - 11

SP - 1325

EP - 1333

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 11

ER -

A 2.5 Approximation Algorithm for the Multi-Via Assignment Problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this