publications

I work on the design and analysis of efficient approximation algorithms for computing near-optimum solutions to combinatorial optimization problems including problems related to linear programming as well as online algorithms for paging and caching.

For explanations of these terms, see this glossary.

Below you can find copies of publications I've authored or coauthored.

papers

• 2008 Flooding overcomes small covering constraints (draft)

  more

  full text

  google scholar

  The paper concerns covering with submodular cost (CSC), a class of optimization problems of the form

  min {c(x) : x ∈ Rⁿ₊ ; (∀ i) x ∈ S_i},

  where the cost c : Rⁿ₊→R₊ is any increasing submodular function and each constraint set S_i is any monotone subset of Rⁿ₊. CSC generalizes mixed integer linear covering programs with box constraints (MICP): min {c ⋅ x : Ax ≥ b; x ≤ u; x ∈ Rⁿ₊; (∀ j ∈ I) x_j ∈ Z}, where A has non-negative entries.

  The paper presents a d-approximation algorithm for CSC, where d is the maximum number of variables on which any constraint depends. The basic algorithm is a simple greedy algorithm: repeatedly choose any unmet constraint and invest equally in all its variables until the constraint is met. Specific implementations include: (i) A nearly linear-time d-approximation algorithm for MICP. (ii) The first on-line d-competitive algorithms for CSC and MICP, including a memoryless randomized algorithm. (On-line CSC includes on-line set cover, rent-or-buy, paging, weighted caching/paging, and file/web caching; the on-line algorithms here generalize classic k-competitive on-line algorithms including LANDLORD and HARMONIC.) (iii) The first sublinear-time distributed d-approximation algorithms for CSC and MICP, requiring O(log n) and O(log² n) rounds (w.h.p.) for the case d=2 and the general case, respectively.

  The approach is similar to the local-ratio method, but deals naturally with variables over arbitrary non-negative domains.

  with Christos Koufogiannakis
• 2008 Incremental medians via online bidding

  more

  full text

  bibtex

  google scholar

  Following Mettu and Plaxton, we study incremental algorithms for the k-medians problem. Such an algorithm must produce a nested sequence F₁⊆ F₂⊆⋅⋅⋅⊆ F_n of sets of facilities. Mettu and Plaxton show that incremental metric medians has a (roughly) 40-competitive deterministic polynomial-time algorithm. We give improved algorithms, including a (24+ε)-competitive deterministic polynomial-time algorithm and a 5.44-competitive, randomized, non-polynomial-time algorithm.
  We also consider the competitive ratio with respect to size. An algorithm is s-size-competitive if, for each k, the cost of F_k is at most the minimum cost of any set of k facilities, while the size of F_k is at most s k. We present optimally competitive algorithms for this problem.
  Our proofs reduce incremental medians to the following online bidding problem: faced with some unknown threshold T>0, an algorithm must submit ``bids'' b>0 until it submits a bid as large as T. The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bribery.
  Our results on cost-competitive incremental medians extend to approximately metric distance functions, incremental fractional medians, and incremental bicriteria approximation.

  Algorithmica 50(455-478):311-322(2008); Latin American Theoretical Informatics 2005 (LATIN)

  with Marek Chrobak, Claire Mathieu and John Noga
• 2008 Online paging and caching (part 14 of Encyclopedia of Algorithms)

  more

  full text

  bibtex

  google scholar

  A brief summary of online paging and caching results, 1985-2002.

  INDEX TERMS: paging, caching, weighted caching, weighted paging, file caching, least recently used (paging algorithm), first in first out (paging algorithm), flush when full (paging algorithm), the Marking algorithm (paging algorithm), Balance algorithm (weighted caching algorithm), Greedy Dual (weighted caching algorithm), Landlord (file caching algorithm), Squid (file caching software), k-server problem, primal-dual algorithms, randomized algorithms, online algorithms, competitive analysis, competitive ratio, loose competitiveness, access-graph model, Markov paging.

  Springer Encyclopedia of Algorithms(2008)
• 2008 Greedy set-cover algorithms (part 7 of Encyclopedia of Algorithms)

  more

  full text

  bibtex

  google scholar

  A brief summary of greedy set-cover algorithms.

  INDEX TERMS: dominating set, greedy algorithm, hitting set, set cover, minimizing a linear function subject to a submodular constraint.

  Springer Encyclopedia of Algorithms(2008)
• 2007 Beating simplex for fractional packing and covering linear programs

  more

  full text

  bibtex

  google scholar

  (Corrected version of FOCS 2007 paper).

  We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+ε of the optimal cost in time O(n+(r+c)log(n)/ε²). For dense problems (with r,c=O(sqrt(n))) the time is O(n+sqrt(n)log(n)/ε²) --- linear even as ε tends to zero. In comparison, previous Lagrangian-relaxation algorithms generally take at least Ω(n log(n)/ε²) time, while (for small ε) the Simplex algorithm typically takes at least Ω(n min(r,c)) time.

  IEEE Symposium on Foundations of Computer Science

  with Christos Koufogiannakis
• 2007 Efficient and effective explanation of change in hierarchical summaries

  more

  full text

  bibtex

  google scholar

  Given a rooted tree whose leaves have numeric labels, label the nodes so that each leaf label equals the sum of the node labels from the root to the leaf. Minimize the number of non-zero node labels. This problem models finding a parsimonius explanation of observed changes in hierarchical data. We give fast algorithms with applications.

  ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

  with Deepak Agarwal, Dhiman Barman, Dimitrios Gunopulos, Flip Korn and Divesh Srivastava
• 2007 Algorithmic approaches to selecting control clones in DNA array hybridization experiments

  more

  full text

  bibtex

  google scholar

  We study the problem of selecting control clones in DNA array hybridization experiments. The problem arises in the OFRG method for analyzing microbial communities. We formulate this as a combinatorial optimization problem called Balanced Covering. We show hardness of approximation results and give a polynomial-time approximation algorithm based on randomized rounding. The algorithm has been implemented and is publicly available as part of a software package called CloneTools.

  Journal of Bioinformatics and Computational Biology 5(4):937-961(2007); Asia Pacific Bioinformatics Conference (APBC2007)

  with Qi Fu, Elizabeth Bent, James Borneman and Marek Chrobak
• 2006 An integrated scheme for fully-directional neighbor discovery and topology management in mobile ad hoc networks

  more

  full text

  bibtex

  google scholar

  This paper is a follow-up to Topology control to simultaneously achieve near-optimal node degree and low path stretch in ad hoc networks. It gives a related heuristic with more extensive empirical evaluation.

  IEEE MASS: International Conference on Mobile Ad-hoc and Sensor Systems

  with Ece Gelal, Gentian Jakllari and Srikanth Krishnamurthy
• 2006 Topology control to simultaneously achieve near-optimal node degree and low path stretch in ad hoc networks

  more

  full text

  bibtex</