Approximation Algorithms

Finding Optimal Geodesic Bridges Between Two Simple Polygons ( with A. Bhosle), submitted for possible journal publication.

Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links ( with A. Bhosle), submitted for possible journal publication.

Approximating Corridors and Tours via Restriction and Relaxation Techniques, (with A. Gonzalez), ACM Transactions on Algorithms, (to appear).

Improved Algorithms for Constructing Hypercube SP-Multicasting Trees (with C. Cipriano), Proceedings of the 21th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '09 (6 pages).

Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links, (with A. Bhosle), Proceedings of the 21th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '09.

Improved Communication Schedules with Buffers {\it Parallel Processing Letters,} Vol 19, No. 1, 129 -- 139, 2009.

Interconnecting Rectangular Areas by Corridors and Tours (with A. Gonzalez), Proceedings of the SIEEEM, Monterrey, Oct. 2008.

Efficient Distributed Algorithms and Protocols for Handling Transient Single Node Failures, (with A. Bhosle), Proceedings of the 20th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '08, (to appear).

Scheduling Independent Tasks to Minimize Computation and Communication Makespan in Distributed Systems, Proceedings of the 20th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '08.

Continuous Delivery Message Dissemination Problems Under the Multicasting Communication Mode, IEEE Transactions Transactions on Parallel and Distributed Systems, Vol. 19, No. 8, pp. 1034 -- 1043, 2008.

Message Dissemination Using Modern Communication Primitives, Handbook of Parallel Computing: Models, Algorithms, and Applications, Eds. J. Reif and S. Rajasekaran, Chapman & Hall / CRC, Jan. 2008.

Message Dissemination Under the Multicasting Communication Mode, Keynote Address, 8th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT'07, pp. 3 -- 4, 2007.

Approximation Algorithms for the Minimum-Length Corridor and Related Problems, (with A. Gonzalez), Proceedings of the 19th Canadian Conference on Computational Geometry, pp. 253-256, 2007.

Handbook on Approximation Algorithms and Metaheuristics, Ed. T. F. Gonzalez, 86 Chapters, Chapman \& Hall / CRC, May 2007.

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.

Restriction, Handbook of Approximation Algorithms and Metaheuristics, Ed. T. F. Gonzalez, Chapter 3, Part I, Chapman & Hall / CRC, May 2007.

Basic Methodologies and Applications, Handbook of Approximation Algorithms and Metaheuristics, Ed. T. F. Gonzalez, Chapter 2, Part I, Chapman & Hall / CRC, May 2007.

Introduction, Overview, and Definitions, Handbook of Approximation Algorithms and Metaheuristics, Ed. T. F. Gonzalez, Chapter 1, Part I, Chapman & Hall / CRC, May 2007.

Improving the Computation and Communication Time with Buffers, Proceedings of the 17th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '05, Phoenix, Az, pp. 336 - 341.

Exact and Approximation Algorithms for finding the Optimal Bridge Connecting Two Simple Polygons, (with A. M. Bhosle), International Journal on Computational Geometry and Applications, Vol 15, No. 6, pp. 609 - 630, Dec. 2005.

Performance Data Collection Using the Hybrid Approach, (with E. Metz and R. Lencevicius), Proceedings of the 10th European Software Engineering Conference / 13th ACM SIGSOFT Symposium on the Foundations of Software Engineering, Lisbon, Portugal, pp. 126 - 135, Sept. 2005.

Wavelength Assignment in Multifiber Optical Star Networks under the Multicasting Communication Mode, (with R. Brandt), Journal of Interconnection Networks, Vol. 6, No. 5, pp. 383 - 406, 2005.

Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs, (with A. M. Bhosle), Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '04, (2004), MIT Cambridge MA, 94--99.

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

An Efficient Algorithm for Gossiping in the Multicasting Communication Environment," IEEE Transactions on Parallel and Distributed Systems, Vol 14, No. 7, pp. 701 -708, 2003.

Multicasting using WDM in Multifiber Optical Star Networks, (with R. Brandt), Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '03, (2003), Marina Del Rey, CA, 56 -- 61.

On Solving Multimessage Multicasting Problems, International Journal of Foundations of Computer Science, Special Issue on Scheduling - Theory and Applications, Vol. 12, No. 6, pp. 791 -- 808, 2001.

Simple Algorithms for MultiMessage Multicasting with Forwarding, Algorithmica, Vol. 29, 2001, pp. 511 -- 533.

Gossiping in the Multicasting Communication Environment, Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS 2001, (6 pages).

Distributed Algorithms for Multimessage Multicasting, Journal of Interconnection Networks, Vol. 1, No. 4, Dec 2000, pp 303 -- 315.

Gossiping with Multicasting Communication Primitives, Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '00, (2000), Las Vegas, NV, Vol. II, 768 -- 773.

Multimessage Multicasting with Bounded Number of Destinations, Proceedings of the 11th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '99, (1999), Cambridge, MA, 495 -- 500.

Distributed Multimessage Multicasting, Proceedings of the Thirteen International Conference On Systems Engineering, pp. CS-43 -- CS-48, Las Vegas, Nevada, August 1999.

Complexity and Approximations for Multimessage Multicasting, Journal of Parallel and Distributed Computing, 55, 1998, 215 -- 235.

On Ensuring MultiLayer Wirability by Stretching Layouts, (with S. Q. Zheng), VLSI Design: An International Journal of Custom--Chip Design, Simulation, and Testing, Vol. 7, No. 4, 1998, 365 -- 383.

Bounded Fan-Out MultiMessage Multicasting, Nordic Journal on Computing, Vol. 5, 1998, 196 -- 213.

Improved Approximation Algorithms for Embedding Hypergraphs in a Cycle, Information Processing Letters, Vol. 67, 1998, 267 -- 271.

Balanced Min and Max Cuts Under the Triangle Inequality, (with T. Murayama), UCSB Department of Computer Science, Technical Report TRCS--98--24, October 1998.

Algorithms for MultiMessage Multicasting With Forwarding, Proceedings of the Tenth ISCA International Conference on Parallel and Distributed Computing Systems PDCS '97, pp. 372 -- 377, New Orleans, LA, 1997.

MultiMessage Multicasting: Complexity and Approximations, Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS), (1997), vol.1, pp. 211 -- 220, Nominated for the Best Paper Award in the Software Technology Track.

Improved MultiMessage Multicasting Approximation Algorithms, Proceedings of the Ninth International Conference on Parallel and Distributed Computing Systems PDCS '96, pp. 456 -- 461, Dijon, France, September 1996.

MultiMessage Multicasting, Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems (Irregular'96), Lecture Notes in Computer Science (1117), Springer, (1996), pp. 217 -- 228.

Proofs for Improved Approximation Algorithms for MultiMessage Multicasting, UCSB Department of Computer Science, Technical Report TRCS--96--17, July 1996.

Pin Redistribution Problem for Multi--Chip Modules: Algorithms and Complexity, (with D. Chang), International Journal of High Speed Electronics and Systems, Special Issue on High Performance CAD for Packaging and Multi--Chip Modules, Vol. 6, No. 3, 1995, pp, 459 -- 475. Also appears in High Performance Design Automation for Multi--Chip Modules and Packages, Selected Topics in Electronics and Systems -- Vol. 5, Edited by J. D. Cho, and P. D. Franzon, World Scientific Publishing Co., 1996 (IBSN 981--02--2307--2).

Complexity Aspects of Two--Dimensional Data Compression, (with H. Bodlaender and T. Kloks), Nordic Journal on Computing, Vol. 4, No. 2, 1995, pp. 462 -- 495.

LP--Free Approximation Algorithm for the Minimum Weight Vertex Cover Problem, Information Processing Letters, Vol. 54, No. 3, 1995, 129 -- 131.

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

A Flow Based Approach to the Pin Redistribution Problem for Multi--Chip Modules, (with D. Chang, and O. H. Ibarra), Proceedings of the GLS--VLSI '94 Conference, March 1994, pp. 114 -- 119.

On Optimal Guillotine Partitions Approximating Optimal d-Box Partitions, (with M. Razzazi, M. Shing and S. Q. Zheng), Computational Geometry: Theory and Applications, Vol. 4, No. 1, 1994, 1 -- 11.

A Computationally Intractable Problem of Simplicial Complexes, (with O. Egecioglu), 6th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC/SFCA '94), DIMACS, May 1994. Also in Seventh SIAM Conference on Discrete Mathematics, Albuquerque NM, June 22--25, 1994.

Switch--Box Routing Under the Two--Overlap Wiring Model, (with K. G. Shashishekhar and S. Q. Zheng), Algorithmic Aspects of VLSI Layout, Eds. M. Sarrafzadeh and D. T. Lee, World Scientific, 1993, 265 -- 308.

An Approximation Algorithm for Routing Around Two Rectangles, (with S. L. Lee), Algorithmic Aspects of VLSI Layout, Eds. M. Sarrafzadeh and D. T. Lee, World Scientific, 1993, 365 -- 397.

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, 1993, 417 -- 428.

Approximation Algorithms, Keynote Address, Ninth International Conference On Systems Engineering, Las Vegas, Nevada, July 1993.

Algorithms for a Class of Min--Cut and Max--Cut Problems, (with T. Murayama), Proceedings of the Third Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science #650, Springer--Verlag, December 1992, pp. 97 -- 105.

Grid Stretching Algorithms for Routing Multiterminal Nets Through a Rectangle, (with S. Q. Zheng), INTEGRATION: the VLSI Journal, Vol. 13, 1992, 153 -- 177.

Covering a Set of Points in Multidimensional Space, Information Processing Letters, Vol. 40, 1991, 181 -- 188.

An Approximation Algorithm for Partitioning a Hyperrectilinear Polytope with Holes, (with M. Razzazi), Proceedings of the Third Canadian Conference on Computational Geometry, August 1991, pp. 183 -- 186.

Properties and Algorithms for Constrained Delaunay Triangulations, (with M. Razzazi), Proceedings of the Third Canadian Conference on Computational Geometry, August 1991, pp. 114 -- 117.

Complexity Aspects of Map Compression, (with H. Bodlaender and T. Kloks), Proceedings of the Data Compression Conference, April 1991, pp. 287 -- 296.

Approximation Algorithms for Covering with Fixed Size Hypersquares and Related Problems, Proceedings of the 29th Annual Allerton Conference on Communications, Control and Computing, October 1990, pp. 838 -- 847.

Multiterminal--Net Routing by Grid Stretching, (with S. Q. Zheng), IEEE International Conference on Computer Design: VLSI in Computers and Processors ( ICCD '90 ), October 1990, pp. 396 -- 399.

An Efficient Divide--and--Conquer Approximation Algorithm for Hyperrectangular Partitions, (with M. Razzazi and S. Q. Zheng), Proceedings of the Second Canadian Conference on Computational Geometry, August 1990, pp. 214 -- 217.

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

Area Bound for the Three--Layer Wirings of a Class of Planar Layouts, (with S. Q. Zheng), Congressus Numerantium, Vol. 74, January 1990, pp. 181 -- 192.

XXVLSI An Approximation Algorithm for Partitioning a Hyperrectilinear Polygon with Holes, (with M. Razzazi), UCSB Technical Report TRCS 90--23, November, 1990.

Complexity of Data Compression for Colored Maps, (with H. Bodlaender and T. Kloks), ALCOM Workshop on Data Structures, Graph Algorithms, and Computational Complexity, Berlin, Germany, October 1990.

Stretching and Three--Layer Wiring Planar Layouts, (with S. Q. Zheng), INTEGRATION: the VLSI Journal, Vol. 8, 1989, pp. 111 -- 141.

Improved Bounds for Rectangular and Guillotine Partitions, (with S. Q. Zheng), Journal of Symbolic Computation, Vol. 7, 1989, pp. 591 -- 610.

An Approximation Algorithm for the Via Placement, (with K. G. Shashishekhar), IEEE Transactions on Computer--Aided Design of Integrated Circuits and Systems, Vol. 8, No. 3, March 1989, pp. 219 -- 228.

Area Bound for the Three--Layer Wirings of a Class of Planar Layouts, (with S. Q. Zheng), Twentieth Southeastern Conference on Combinatorics, Graph Theory and Computing, February 1989.

A Suboptimal Solution to the Via Placement Problem, (with K. G. Shashishekhar), Proceedings of the 25th Annual Allerton Conference on Communications, Control and Computing, October 1987, pp. 377 -- 386.

Three Layer Wirability of Planar Layouts, (with S. Q. Zheng), Proceedings of the 25th Annual Allerton Conference on Communications, Control and Computing, October 1987, pp. 387 -- 396.

Layer Assignment for Planar Layouts, (with S. Q. Zheng), IEEE International Conference on Computer Design: VLSI in Computers and Processors ( ICCD '87 ), October 1987, pp. 278 -- 281.

A 1.60 Approximation Algorithm for Routing Multiterminal Nets Around a Rectangle, (with S. L. Lee), SIAM Journal on Computing, Vol. 16, No. 4, August 1987, pp. 669 -- 704.

Three--Layer Channel Routing Multi--Terminal Nets, (with S. Q. Zheng), UCSB Technical Report #TRCS 87--13, August 1987.

Routing Multiterminal Nets Around a Rectangle, (with S. L. Lee), IEEE Transactions on Computers, Vol. C--35, No. 6, June 1986, pp. 543 -- 549.

An Approximation Algorithm for Routing Two--Terminal Nets Around Two Rectangles, (with S. L. Lee), Proceedings of the 24th Annual Allerton Conference on Communication, Control and Computing, October 1986, pp. 550 -- 559.

Improved Bounds for Rectangular and Guillotine Partitions, (with S. Q. Zheng), Proceedings of the 24th Annual Allerton Conference on Communication, Control and Computing, October 1986, pp. 334 -- 343.

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

Bounds for Partitioning Rectilinear Polygons, (with S. Q. Zheng), Proceedings of the Computational Geometry Conference, June 1985, pp. 281 -- 287.

An Approximation Algorithm for the Multi--Via Assignment Problem, IEEE Transactions on Computer--Aided Design of Integrated Circuits and Systems, Vol. CAD--3, No. 4, October 1984, pp. 257 -- 264.

On the Computational Complexity of Path Covering Problems, (with S. Ntafos), Journal of Computer and Systems Sciences, Vol. 29, No. 1, October 1984, pp. 225 -- 342.

Near--Optimal Routings of Multi--Nets Around a Rectangle, (with S. L. Lee), Proceedings of the 22nd Annual Allerton Conference on Communications, Control and Computing, October 1984, pp. 498 -- 507.

Optimal and Near--Optimal Routing Around a Rectangle, (with S. L. Lee), ORSA/TIMS National Joint Meeting, Dallas Texas, November 1984.

An Approximation Algorithm for the Via Assignment Problem, Proceedings of the 1983 International Conference on Computer--Aided Design ( ICCAD 83 ), Santa Clara, CA, September 1983, pp. 125 -- 128.

Approximation Algorithms for PLA Folding, Technical Report #128, The University of Texas at Dallas, March 1983.

Preemptive Scheduling of Parallel Processors, ORSA/TIMS Joint National Meeting, Houston Texas, October 1981.

An Efficient Approximate Algorithm for the Kolmogorov--Smirnov and Lilliefors Tests, (with S. Sahni and W. R. Franta), Journal of Statistical Computation and Simulation, Vol. 6, 1978, pp. 257 -- 263.

Flowshop and Jobshop Schedules: Complexity and Approximation, (with S. Sahni), Operations Research, Vol. 26, No. 1, January--February 1978, pp. 36 -- 52.

Bounds for LPT Schedules for Uniform Processors, (with O. H. Ibarra and S. Sahni), SIAM Journal on Computing, Vol. 6, No. 1, March 1977, pp. 155 -- 166.

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

P--Complete Problems and Approximate Solutions, (with S. Sahni), Proceedings of the 15th Annual IEEE Symposium on Switching and Automata Theory, October 1974, pp. 28 -- 32.