Most Significant Previous Research Contributions

Teofilo F. Gonzalez

  • Research Areas
  • (A) Minimum Edge Length Partitions
    (B) Wire Routing
    (C) Clustering
    (D) Openshop Scheduling
    (E) NP-hard Approximation Problems

  • Research Accomplishments
  • (A) Minimum Edge Length Partitions

    The following series of papers address the problem of partitioning a rectangle with interior points into rectangles so that the length of the partitioning line segments is least possible as well as the generalization of this problem to multidimensional space. This problem has applications in VLSI routing and our contribution was developing provably good solutions to this problem. The three different algorithm take increasingly more computation time, but as the time complexity increases the solutions generated are provably better. The algorithms are based on greedy, divide-and-conquer and dynamic programming. The general technique for approximation is restriction which in this case means generating optimal or suboptimal guillotine partitions. This same approach was subsequently applied to approximate other problems. We were able to extend our results to generalizations of our problem to multi-dimensional space. Other researchers working on these problems include: Lingas (Sweden), Rivest (MIT), Du (UTD), Pinter (Israel), Levcopoulos (Sweden), etc.

    Approximation Algorithms for Partitioning Rectilinear Polygons with Interior Points, (with S. Q. Zheng), Algorithmica, Vol. 5, pp. 11 -- 42, 1990.

    An Efficient Divide-and-Conquer Approximation Algorithm for Partitioning D--Boxes, with M. Razzazi, and S. Q. Zheng, International Journal on Computational Geometry and Applications, Vol. 3, No. 4, pp. 417 -- 428, 1993.

    On Optimal Guillotine Partitions Approximating Hyper-rectangular Partitions, with M. Razzazi, M. Shing and S. Q. Zheng, Computational Geometry: Theory and Applications, Vol. 4, pp. 1 -- 11, 1994.

    A summary of these results appears in

    Minimum Edge Length Rectangular Partitions, (with S. Q. Zheng), Handbook of Approximation Algorithms and Metaheuristics, Ed. T. F. Gonzalez, Chapter 54, Part V, Chapman & Hall / CRC, May 2007.

    (B) Wire Routing

    Our work on VLSI routing problems was among the first when VLSI became a popular area for algorithmic research. Our two most significant papers are discussed below.

    One of the basic problems in VLSI routing is the two-terminal net routing around a rectangle to minimize the area of the smallest rectangle enclosing the wire layout. We developed the first linear time algorithm for this problem. This is a simple and elegant algorithm with a complex correctness proof. The main idea was to reduce the problem to one of four problems, each of which can be solved by a greedy technique. Subsequently other research groups developed similar results, but these algorithms either generated near-optimal solutions or the problems were slight variations of the original problem. In other publications we extended our work to multi-termial nets. Our results appear in the following paper. Other researchers that studied this problem include: Preparata (Brown), Sarrafzadeh (UCLA), LaPaugh (Princeton), Nishiseki (Tohoku), Frank (Hungry) Tardos (Cornell), JaJa (Maryland), Vishkin (Maryland), etc.

    A Linear Time Algorithm for Optimal Wiring Around a Rectangle, with S. L. Lee, Journal of the Association for Computing Machinery, Vol. 35, No. 4, pp. 810 -- 832, 1988.

    Another basic routing problem in VLSI is the two-terminal channel routing problem. We developed a simple technique to solve this problem. The proof of correctness is also simple and elegant. Other researchers that worked on this problem include: Preparata (Brown), Sarrafzadeh (UCLA), Brown (UIUC), etc.

    Single Phase Three--Layer Channel Routing Algorithms, with S. Q. Zheng, INTEGRATION, the VLSI Journal, 17, pp. 141 -- 151, 1994.

    (C) Clustering

    A problem which has encountered a large set of applications is that of clustering a set of points into a given number of clusters so that the farthest distance between two points in the same cluster is minimized. I developed an efficient approximation algorithm for this problem and showed that it is best possible unless P = NP. The algorithm has found applications in many different areas, e.g., color quantization, databases, web applications, biofinformatics, etc. The our algorithm provides the best possible solution. This result, which has received numerous citations during the last two decades, is one of the top cited papers published in the Theoretical Computer Science Journal. Other researchers that worked on this problem include: Bruckner (Germany), Hochbaum (Berkeley), Shmoys (Cornell), etc.

    Clustering to Minimize the Maximum Inter-Cluster Distance, Journal of Theoretical Computer Science, No. 38, pp. 293 -- 306, 1985.

    (D) Openshop Scheduling

    Gonzalez and Sahni are the originators of the open shop scheduling problem. They defined the open shop scheduling problem and developed an efficient algorithm for preemptive scheduling independent jobs. The problem has found applications in telecommunications, communication networks, parallel algorithms, and scheduling theory, etc. Their original algorithm has not be improved, except when there is a constant number of machines or jobs (see paper below). Openshop scheduling is now as popular as flowshop and jobshop scheduling,which have been classical scheduling problems for more than 50 years. A large number of researchers working in the area of scheduling algorithms have worked on openshop problems.

    Open Shop Scheduling to Minimize Finish Time, with S. Sahni, Journal of the Association for Computing Machinery Vol. 23, No. 4, pp. 665 -- 679, 1976.

    A Note on Open Shop Preemptive Schedules, IEEE Transactions on Computers, Vol. C-28, No. 10, pp. 782 -- 786, 1979.

    A summary of these results appears in

    Open Shop Scheduling, , Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Ed. Y. J.-T. Leung, Chapter 6, Part II, Chapman & Hall / CRC, May 2004.

    Other scheduling work includes (see the CV): scheduling jobs under tree-like precedence constraints on identical machines, preemptive and non-preemptive uniform processor scheduling, and flow shop and job shop scheduling. Our work was innovative because it introduced new techniques to solve preemptive scheduling problems. The following papers on preemptive scheduling are important as they identified a new algorithmic research area that became popular in the mid-90s. Other researchers who worked on these problems include: Coffman (Columbia), Muntz (UCLA), Sethi (Lucent), Horvath (Penn State), C. Liu (UIUC), J. Liu (UIUC), etc.

    Preemptive Scheduling of Uniform Processor Systems, (with S. Sahni) Journal of the Association for Computing Machinery, Vol. 25, No. 1, January 1978, pp. 92 -- 101.

    A New Algorithm for Preemptive Scheduling Trees, (with D. B. Johnson), Journal of the Association for Computing Machinery, Vol. 27, No. 2, April 1980, pp. 287 -- 312.

    (E) NP-hard Approximation Problems

    Another well-know result by Gonzalez and Sahni, was establishing (for the first time) that for a class of problems finding an approximate solution is as difficult (computationally) as generating the optimal one. This work has received numerous citations and was the first paper that addressed inapproximability. In the 90s it became very popular to establish inapproximability results.

    P-Complete Approximation Problems, with S. Sahni, Journal of the Association for Computing Machinery Vol. 23, No. 3, pp. 555 -- 565, 1976.



    I have made other important contributions (see my CV), but I feel the above papers are my most significant contributions.