I have annotated each paper with a partial list of keywords using the
following key:
ApA = Approximation Algorithms;
CoL = Computational Learning;
DiA = Distributed Algorithms;
ElN = Admission Control and Routing in Deregulated Electric
Power Networks;
ErC = Error-Correcting Codes;
ExA = Experimental Analysis of Algorithms;
GrC = Graph/Hypergraph Coloring;
InW = Internet/WWW-related technologies;
NeD = Network Design;
PaA = Parallel Algorithms;
RaC = Randomness and Computation;
ReS = Resource Allocation and Scheduling;
RoA = Routing Algorithms;
RWA = Routing and Wavelength Assignment in Optical Networking;
Oth = Other topics not covered above.
Please email me if you
would like copies of some of these papers.
Journal Publications
- New Algorithmic Aspects of the Local Lemma with Applications to Routing
and Partitioning,
with F. T. Leighton,
C.-J. Lu
and S. B.
Rao.
Accepted for publication in SIAM Journal on Computing.
[ApA, InW, RaC, RoA, RWA]
- Improved Bounds on the Sample Complexity of Learning, with
Y. Li and
P. M. Long.
Journal of Computer and System
Sciences, Vol. 62, 516-527, 2001. [CoL]
- A Constant-Factor Approximation Algorithm for Packet Routing
and Balancing Local vs. Global Criteria, with C. P. Teo.
SIAM Journal on Computing, Vol. 30, 2051-2068, 2001.
[ApA, InW, RoA]
- The One-Inclusion Graph Algorithm is Near-Optimal for the
Prediction Model of Learning, with
Y. Li and
P. M. Long.
IEEE Transactions on Information Theory,
Vol. 47, 1257-1261, 2001. [CoL]
- Better Approximation Guarantees for Job-Shop Scheduling, with
L.
A. Goldberg,
M.
S. Paterson and E. Sweedyk.
SIAM Journal on Discrete Mathematics, Vol. 14, 67-92, 2001.
[ApA, RaC, ReS]
- Contention Resolution with Constant Expected Delay, with
L.
A. Goldberg,
P. D. MacKenzie, and
M.
S. Paterson. Journal of the ACM, Vol. 47,
1048-1096, 2000.
[DiA, InW, RaC, ReS]
- Improved Algorithms via Approximations of Probability
Distributions, with S. Chari and P. Rohatgi.
Journal of Computer and System
Sciences, Vol. 61, 81-107, 2000. [PaA, RaC]
- Approximation Algorithms for Disjoint Paths and Related Routing and
Packing Problems, with
A. Baveja. Mathematics of
Operations Research, Vol. 25, 255-280, 2000.
[ApA, InW, RaC, ReS, RoA, RWA]
- Retrieval Scheduling For Collaborative Multimedia
Presentations, with Ping Bai and
B. Prabhakaran.
ACM/Springer-Verlag Multimedia Systems Journal, Vol. 8,
146-155, 2000.
[InW, ReS]
- Low Discrepancy Sets Yield Approximate Min-Wise Independent
Permutation Families,
with
M. Saks,
S. Zhou
and D. Zuckerman,
Information Processing Letters, Vol. 73, 29-32, 2000.
[InW, RaC]
- Improved Bounds and Algorithms for Hypergraph 2-coloring,
with
J. Radhakrishnan,
Random
Structures & Algorithms, Vol. 16, 4-32, 2000. [GrC,
RaC]
- Approximating Low-Congestion Routing and Column-Restricted
Packing Problems, with
A. Baveja,
Information Processing Letters, Vol. 74, 19-25, 2000.
[ApA, InW, RaC, RoA]
- Improved Approximation Guarantees for Packing and Covering
Integer Programs,
SIAM Journal on Computing, Vol. 29, 648-670, 1999.
[ApA, RaC]
- Computing with Very Weak Random Sources, with
D. Zuckerman,
SIAM Journal on Computing, Vol. 28, 1433-1459, 1999.
[RaC]
- Explicit OR-Dispersers with Polylogarithmic Degree, with
M. Saks
and S. Zhou,
Journal of the ACM, Vol. 45, 123-154, 1998. [RaC]
- Approximating Hyper-Rectangles: Learning and Pseudo-Random
Sets, with P.
Auer and
P. M. Long, Journal of
Computer and System Sciences, Vol. 57, 376-388, 1998.
[CoL, RaC]
- Improved Parallel Approximation of a Class of Integer Programming
Problems, with N. Alon,
Algorithmica, Vol. 17, 449-462, 1997.
[PaA, RaC]
- Randomized Distributed Edge Coloring via
an Extension of the Chernoff-Hoeffding Bounds, with
A. Panconesi,
SIAM Journal on Computing, Vol. 26, 350-368, 1997.
[DiA, GrC, RaC, ReS]
- On the Complexity of Distributed Network Decomposition,
with A. Panconesi,
Journal of Algorithms, Vol. 20,
356-374, 1996. [DiA, ReS]
- Randomness-Optimal Unique Element Isolation with
Applications to Perfect Matching and Related Problems,
with S. Chari and P. Rohatgi,
SIAM Journal on Computing, Vol. 24, 1036-1050, 1995.
[PaA, RaC]
- Chernoff-Hoeffding Bounds for Applications with Limited
Independence, with J. P. Schmidt and A. Siegel,
SIAM Journal on Discrete Mathematics, Vol. 8, 223-250,
1995. [RaC, ReS]
- The Local Nature of Delta-Coloring and its Algorithmic
Applications, with A. Panconesi,
Combinatorica, Vol. 15,
255-280, 1995. [DiA, GrC]
- On Finding the Minimum Bandwidth of Interval Graphs, with R.
Mahesh and
C.
Pandu Rangan, Information and Computation,
Vol. 95, 218-224, 1991. [Oth]
- Efficient Algorithms for the Minimum Weighted Dominating
Clique Problem on Permutation Graphs, with
C.
Pandu Rangan, Theoretical Computer
Science, Vol. 91, 1-21, 1991. [Oth]
Refereed Conference Publications
- Distributions on Level-Sets with Applications to
Approximation Algorithms. To appear,
IEEE Symposium on Foundations of Computer
Science (FOCS), 2001. [ApA, RaC, RoA]
- Finding Large Independent Sets of Hypergraphs in Parallel,
with
H. Shachnai.
ACM Symposium on Parallel Algorithms and
Architectures (SPAA), 2001.
[PaA, RaC]
- Experimental Analysis of Algorithms for
Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power
Industry, with
C. Barrett, D. Cook, V. Faber, G. Hicks,
A. Marathe,
M. Marathe,
Y. J. Sussmann,
and H. Thornquist.
To appear, Workshop on Algorithm Engineering (WAE),
2001. [ElN, ExA, RaC]
- Approximation Algorithms for Partial
Covering Problems, with
R. Gandhi
and
S. Khuller.
International Colloquium
on Automata, Languages, and Programming (ICALP), 2001.
[ApA, RaC]
- New Approaches to Covering and Packing Problems.
ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 567-576, 2001.
[ApA, PaA, RaC]
- Domatic Partitions and the Lova'sz Local Lemma.
ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 922-923, 2001.
[ApA, RaC]
- Wavelength Rerouting in Optical Networks, or
the Venetian Routing Problem, with
A. Caprara,
G. Italiano,
G. Mohan, and
A. Panconesi.
Third International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems
(APPROX), pages 72-83, 2000. [ApA, InW, RWA]
- The Value of Strong Inapproximability Results for Clique.
ACM Symposium on Theory of Computing (STOC),
pages 144-152, 2000.
[ApA, RaC]
- Optimal Design of Signaling Networks for Internet Telephony,
with
K. G.
Ramakrishnan,
K.
Kumaran, M. Aravamudan, and
S. Naqvi. IEEE Conference on Computer
Communications (INFOCOM), pages 707-716, 2000.
[InW, NeD, RaC]
- Improved Bounds on the Sample Complexity of Learning, with
Y. Li and
P. M. Long.
ACM-SIAM
Symposium on Discrete Algorithms (SODA),
pages 309-318, 2000. [CoL]
- Application-layer Broker for Scalable Internet Services with
Resource Reservation, with P. Bai and
B. Prabhakaran.
Seventh
ACM Multimedia Conference (MM '99),
pages 103-106, 1999. (Poster paper.)
[InW, ReS]
- Low Discrepancy Sets Yield Approximate Min-Wise Independent
Permutation Families,
with
M. Saks,
S. Zhou
and D. Zuckerman,
Third International Workshop on
Randomization and Approximation Techniques in Computer Science
(RANDOM), pages 11-15, 1999. [InW, RaC]
- New Algorithmic Aspects of the Local Lemma with Applications to Routing
and Partitioning,
with F. T. Leighton
and S. B.
Rao,
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 643-652,
1999. [ApA, InW, RaC, RoA, RWA]
- Improved Bounds and Algorithms for Hypergraph Two-coloring,
with
J. Radhakrishnan,
IEEE Symposium on Foundations of Computer
Science (FOCS), pages 684-693, 1998.[GrC, RaC]
- Low-bandwidth Routing and Electrical Power Networks, with
D. Cook, V. Faber,
M. Marathe,
and
Y. J. Sussmann,
International Colloquium
on Automata, Languages, and Programming (ICALP),
pages 604-615, 1998. [ApA, ElN, RaC]
- Multicommodity Flow and Circuit Switching,
with F. T. Leighton
and S. B.
Rao, Hawaii International Conference on System Sciences
(HICSS), pages 459-465, 1998. [ApA, InW, RaC, RWA]
- Improved Approximations for Edge-disjoint Paths, Unsplittable
Flow, and Related Routing Problems,
IEEE Symposium on Foundations of Computer Science (FOCS),
pages 416-425, 1997. [ApA, InW, RaC, ReS, RoA, RWA]
- Mechanism Design for Intellectual Property Rights
Protection, with
P. S. Giridharan, International Conference on Information Systems
(ICIS), 1997. [Oth]
- Approximating Hyper-Rectangles: Learning and Pseudo-Random
Sets, with P.
Auer and P. M. Long,
ACM Symposium on Theory of Computing (STOC),
pages 314-323,
1997. [CoL, RaC]
- A Constant-Factor Approximation Algorithm for Packet Routing,
and Balancing Local vs. Global Criteria, with C. P. Teo,
ACM Symposium on Theory of Computing (STOC),
pages 636-643, 1997. [ApA, InW, RoA]
- Better Approximation Guarantees for Job-Shop Scheduling, with
L.
A. Goldberg,
M.
S. Paterson and E. Sweedyk,
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 599-608, 1997. [ApA, RaC, ReS]
- Improving the Discrepancy Bound for Sparse Matrices: Better
Approximations for Sparse Lattice Approximation Problems,
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 692-701, 1997. [ApA, GrC, RaC]
- Improved Parallel Approximation of a Class of Integer Programming
Problems, with N. Alon,
International Colloquium
on Automata, Languages, and Programming (ICALP),
pages 562-573, 1996. [PaA, RaC]
- An Extension of the Lova'sz Local Lemma, and its
Applications to Integer Programming,
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 6-15, 1996. [ApA, GrC, RaC]
- Splitters and Near-optimal Derandomization, with
M. Naor and
L. J. Schulman,
IEEE Symposium on Foundations of Computer
Science (FOCS), pages 182-191, 1995.
[RaC]
- Contention Resolution with Bounded Delay, with M.
S. Paterson,
IEEE Symposium on Foundations of Computer
Science (FOCS), pages 104-113, 1995.
[DiA, RaC, ReS]
- Explicit Dispersers with Polylog Degree, with
M. Saks
and S. Zhou,
ACM Symposium on Theory of Computing (STOC),
pages 479-488, 1995. [RaC]
- Improved Approximations of Packing and Covering Problems,
ACM Symposium on Theory of Computing (STOC),
pages 268-276, 1995. [ApA, RaC]
- Computing with Very Weak Random Sources,
with D. Zuckerman,
IEEE Symposium on Foundations of Computer
Science (FOCS), pages 264-275, 1994. [RaC]
- Improved Algorithms via Approximations of Probability
Distributions, with S. Chari and P. Rohatgi, ACM
Symposium on Theory of Computing (STOC),
pages 584-592, 1994. [PaA, RaC]
- Randomness-Optimal Unique Element Isolation, with
Applications to Perfect Matching and Related Problems,
with S. Chari and P. Rohatgi,
ACM Symposium on Theory of Computing (STOC),
pages 458-467, 1993. [PaA, RaC]
- Chernoff-Hoeffding Bounds for Applications with Limited
Independence, with J. P. Schmidt and A. Siegel,
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 331-340, 1993. [RaC, ReS]
- Fast Randomized Algorithms for Distributed Edge Coloring,
with A. Panconesi,
ACM Symposium on Principles of
Distributed Computing (PODC),
pages 251-262, 1992. [DiA, GrC, RaC, ReS]
- Improved Distributed Algorithms for Coloring and Network
Decomposition Problems, with A. Panconesi, ACM
Symposium on Theory of Computing (STOC),
pages 581-592, 1992. [DiA, GrC]
Chapters in Books and Survey Articles
- Combinatorial Problems Arising in Deregulated Electrical
Power Industry: Survey and Future Directions, with
D. Cook, G. Hicks, V. Faber,
M. Marathe,
Y. J. Sussmann,
and
H. Thornquist,
Approximation and Complexity in
Numerical Optimization: Continuous and Discrete Problems
(P. M. Pardalos, Editor), Kluwer Academic Publishers,
pages 138-162, 2000. [ApA, ElN, RaC]
- Low-discrepancy Sets for High-dimensional Rectangles: A Survey,
Bulletin of
the European Association for Theoretical Computer
Science, Number 70, pages 67-76, 2000. [ErC, RaC]
- A Survey of the Role of Multicommodity Flow and Randomization in
Network Design and Routing, Randomization Methods in Algorithm
Design
(P. M. Pardalos, S. Rajasekaran and J. Rolim, editors),
American Mathematical Society,
Series in Discrete Mathematics and Theoretical Computer Science,
Volume 43, pages 271-302, 1999. [ApA, InW, RaC, RoA]
- Approximation Algorithms via Randomized Rounding: a Survey.
Lectures on Approximation and Randomized
Algorithms (M. Karonski and H. J. Promel, editors),
Series in
Advanced Topics in Mathematics,
Polish Scientific Publishers PWN, Warszawa,
pages 9-71, 1999. [ApA, InW, RaC, RoA]
- Scheduling and Load-balancing via Randomization,
Proc. Pre-Conference Workshop on Randomized Algorithms,
Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, 1997. [RaC, ReS]
- The Role of Randomness in Computation,
BRICS Notes Series NS-95-6, Basic Research Institute in Computer
Science, Denmark, 1995. [RaC]
Technical Reports and Theses
- Techniques for Probabilistic Analysis and Randomness-Efficient
Computation, TR 93-1378, Department of Computer
Science, Cornell University,
1993. [DiA, GrC, PaA, RaC, ReS]
- A Generalization of Brooks' Theorem, TR 92-1302, Department of
Computer Science, Cornell University, 1992. [DiA, GrC]
- Fast Algorithms for Some Problems on Interval and
Permutation Graphs, B. Tech. Thesis, Department of Computer
Science and Engineering, Indian Institute of Technology, Chennai,
1989. [Oth]
Other Papers
- Fast and Efficient Bandwidth Reservation
for Robust Routing, with L. Fleischer, A. Meyerson,
I. Saniee, and B. Shepherd,
DIMACS Mini-Workshop on Quality of
Service Issues in the Internet, 2001.
[ApA, InW, ReS, RoA]