Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

The following is a ``very coarse" categorization; in each the papers are in roughly reverse chronological order.

• Uncertainty, Games & Partial information based optimization
• Algorithms for Data Streams
• Clustering & Facility Location problems (minus Streams)
• Network Design and misc. Approximation Algorithms
• Non-Streaming Database papers

Uncertainty, Games & Partial Information based Optimization

• Iterated Allocations with Delayed Feedback
  (with K. Munagala and M. Pal).
• Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions
  (with T. Chakraborty, E. Even-Dar, Y. Mansour, and S. Muthukrishnan).
• Selective Call Out and Real Time Bidding
  (with T. Chakraborty, E. Even-Dar, Y. Mansour, and S. Muthukrishnan).
• Exceeding Expectations and Clustering Uncertain Data
  (with K. Munagala).
• Approximation algorithms for restless bandit problems
  (with K. Munagala and P. Shi).
  This paper supercedes and generalizes the results in Partial-information based Stochastic Control paper.
• Multi-Armed Bandits with Metric Switching costs
  (with K. Munagala). This is subsequent work following this paper on Sequential design which is an expanded version of the result on budgeted learning.
• Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems
  (with K. Munagala).
  The above is a cleaned up version of model driven optimization
  
• How to probe for an extreme value
  (with A. Goel and K. Munagala).
  The above is a cleaned up version of this .
• Performance guarantees ithrough partial information based control in multi-channel wireless networks
  (with K. Munagala and S. Sarkar )

The above paper is a technical report which significantly extends and improves the results in here and there .

Algorithms for Data Streams

• Graph Sketches: Sparsification, Spanners, and Subgraphs
  (with K. Ahn and A. McGregor)
• Analyzing Graph Structure via Linear Measurements
  (with K. Ahn and A. McGregor)
• Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
  (with K. Ahn)
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
  (with K. Ahn)
• Graph Sparsification in the Semi- streaming Model
  (with K. Ahn)
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
  (with Z. Huang)
• Dynamic Join Optimization in Multi-Hop Wireless Sensor Networks
  (with S. Mihaylov, M. Jacob and Z. Ives).

Tight results for clustering and summarizing data streams


• A substrate for In-Network Sensor Data Integration
  (with S. Mihaylov, M. Jacob and Z. Ives).
• Tight lower bounds for multipass stream computation via pass elimination
  (with A. McGregor).
• Stream Order and Order Statistics: Quantile estimation in Random Order Streams
  (with A. McGregor). This combines upper bounds and lower bounds .
• Sketching Information Divergences
  (with P. Indyk and A. McGregor). This improves upon an older version in the conference proceedings, which is here .
• A Note on Linear Time Algorithms for Maximum Error Histograms
  (with K. Shim). This is not a paper in the streaming model, but in the same genre of constructing small space representations.
• Space Efficient Sampling
  (with A. McGregor)
• Streaming and Sublinear Approximation of Entropy and Information Distances
  (with A. McGregor and S. Venkatasubramanian)

  The above is the SODA version, an old extended version is here .

• Approximation Algorithms for Wavelet Transform Coding of Data Streams
  (with B. Harb)

  The above is an extended version of this paper in Soda 06, which in turn is improves this .

• On the Space-time of Optimal, Approximation and Streaming Algorithms for Synopsis Construction Problems
  Extended version.
• Approximation and Streaming Algorithms for Histogram Construction Problems
  (with N. Koudas and K. Shim)

  The above paper is an extended and significantly improved version of this .
  The paper also improves this where we extended histogram construction to
  sliding window streams. The above paper also subsumes part of this where
  we looked at relative error measures and proposed a block by block algorithm for
  histogram construction. The above paper assumes a simpler model of streaming,
  for the full monty, see the next paper.

• Fast Small-space Algorithms for Approximate Histogram Maintenance
  (with A. C. Gilbert, P. Indyk, Y. Kotidis, S. Muthukrishnan and M. J. Strauss)

  The above paper works on a stream of updates for 1 dimension and
  forms the basis of our work on multidimensional histograms in this .

• Histogramming Data Streams with Fast per Item Processing
  (with P. Indyk, S. Muthukrishnan and M. J. Strauss)

  The above paper proves a nice correspondence between sum of squares errors for wavelets and histograms.

• Near-Optimal Sparse Fourier Representations via Sampling
  (with A. C. Gilbert, P. Indyk, S. Muthukrishnan and M. J. Strauss)
• Inferring Mixtures of Markov Chains
  (with T. Batu and S. Kannan) Conference version.
• XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data
  (with C. Kim and K. Shim) Conference version.
• Compression of Partially Ordered Strings
  (with R. Alur, S. Chaudhuri, K. Etessami and M. Yannakakis)
• Correlating Synchronous and Asynchronous Data Streams
  (with D. Gunopoulos and N. Koudas) Conference version.
• Clustering Data Streams: Theory and Practice
  (with A. Meyerson, N. Mishra, R. Motwani, and L. O'callaghan)

  This paper combines the papers this , and that .

Clustering & Facility Location problems

• Asymmetric K-center is Omega(log* n) hard to approximate
  (with J. Chuzhoy, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer, and J. Naor).
• Improved Combinatorial Algorithms for Facility Location Problems
  (with M. Charikar)

  The above contains a local search based facility location algorithm. The previous version
  also contained the full proof of the integrality gap of the K-median problem being at most 4.

• A Constant Factor Approximation for the K-Median Problem
  (with M. Charikar, E. Tardos and D. Shmoys)

  The above is an extended version. The conference version also contained some
  extra results on the capacitated problem.

• A Constant Factor Approximation Algorithm for the Fault-tolerant Facility Location Problem
  (with A. Meyerson and K. Munagala) Extended version.
• Improved Algorithms for the Data Placement Problem
  (with K. Munagala) Conference version.
• Generalized Clustering
  (with K. Munagala) Conference version.
• ROCK - A Robust Clustering Algorithm for Categorical Attributes,
  (with R. Rastogi, and K. Shim) Extended version.
• Greedy strikes back: Improved Facility Location Algorithms.
  (with Samir Khuller) Extended version.
• CURE - An Efficient Clustering Algorithm for Large Databases,
  (with R. Rastogi, and K. Shim) Extended version.

• Facility Location with Dynamic Distance Functions
  (with R. Bhatia, S. Khuller and Y. Sussmann) Extended version.

Network Design and misc. Approximation Algorithms

• Machine minimization for scheduling jobs with interval constraints
  (with J. Chuzhoy, S. Khanna, and J. Naor) Conference version.
• Approximating Steiner k-cuts
  (with C. Chekuri and J. Naor ) Extended version.
• Throughput Maximization of Real-Time Scheduling with Batching
  (with A. Bar-noy, Y. Katz, J. Naor, B. Schieber and H. Shachnai) Conference version.
• Capacitated Vertex Covering with Applications
  (with R. Hassin S. Khuller and E. Or) Conference version.
• A Constant Factor Approximation for the Single-Sink Edge Installation Problem
  (with A. Meyerson and K. Munagala). Extended version. Conference version is here .
• Hierarchical Placement and Network Design Problems
  (with A. Meyerson and K. Munagala) Conference version. This paper introduces several different reductions that are useful for multilevel problems.
• Nested Graph Dissection and Approximation Algorithms Extended version.
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
  (with G. Even and B. Schieber) Extended version.
• Approximating the Throughput of Real-time Multiple Machine Scheduling
  (with A. Bar-noy, J. Naor and B. Schieber) Extended version.
• Efficient Recovery from Power Outage
  (with A. Moss, J. Naor and B. Schieber) Conference version.
• Approximating a finite metric by small number of trees
  (with M. Charikar, C. Chekuri, A. Goel, and S. Plotkin) Conference version.
• Multicasting in Heterogeneous Networks
  (with A. Bar-noy, J. Naor and B. Schieber) Extended version.
• Rounding via trees : Deterministic approximation algorithms for Group Steiner trees and k - median
  (with M. Charikar, C. Chekuri, and A. Goel) Conference version.
• Approximation Algorithms for Directed Steiner Trees.
  (with M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel and M. Li) Extended version.
• Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets.
  (with S. Khuller) Extended version.
• Approximation Algorithms for Connected Dominating Sets.
  (with S. Khuller) Extended version.

Non-Streaming Database papers

• Improving the Performance of List Intersection.
  (with D. Tsirogiannis and N. Koudas).
• Learning to create data integrating queries
  (with P. Talukdar, M. Jacob, M. Mehmood, K. Crammer, Z. Ives, and F. Pereira)
• Ad-hoc aggregations of ranked lists in the presence of hierarchies
  (with N. Bansal, and N. Koudas)
• Approximate XML Joins
  (with H. Jagadish, N. Koudas, D. Srivastava, and T. Yu) Conference version.
• Merging the Results of Approximate Match Operations
  (with N. Koudas, A. Marathe, and D. Srivastava) Conference version.
• Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints
  (with D. Gunopoulos, N. Koudas, D. Srivastava, and M. Vlachos) Conference version.
• Fast Algorithms For Hierarchical Range Histogram Construction
  (with N. Koudas, and D. Srivastava) Conference version.