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,
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.
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.
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),
Single Phase Three--Layer Channel Routing Algorithms, with S. Q. Zheng,
INTEGRATION, the VLSI Journal, 17, pp. 141 -- 151, 1994.
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,
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.
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
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.
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.
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.