Publications

1. An Online Algorithm for Maximizing Submodular Functions. With Matthew Streeter.
   Tech Report CMU-CS-07-171. BibTeX. Upcoming conference verion to appear in NIPS 2008.
   We present efficient online algorithms for generalizations of Maximum k-Coverage and Min-Sum Set Cover. Our algorithms achieve asymptotically optimal approximation ratios in a natural regret model (assuming P != NP), and have many practical applications, such as speeding up solvers for boolean satisfiability or integer programming.
   
   
2. All-Norms and All-L_p-Norms Approximation Algorithms. With Anupam Gupta, Amit Kumar, and Kanat Tangwongsan.
   Tech Report CMU-CS-07-153. BibTeX. Upcoming conference verion to appear in FSTTCS 2008.
   We examine approximation algorithms that simultaneously perform well on all norms, or on all L_p norms. We show that the greedy algorithm for set cover simultaneously O(p) approximates the L_p norm of the cover time vector for all values of p, and that no efficient algorithm can do better than O(p) for any fixed value of p. We also present algorithms and structural results for other problems such as k-facility-location, TSP, and average flow-time minimization.
   
   
3. Uniquely Represented Data Structures for Computational Geometry. With Guy Blelloch and Virginia Vassilevska. SWAT 2008. A more detailed technical report version is available as well. BibTeX
   We build on earlier results for Strongly History-Independent Hashing, and develop uniquely represented data structures for several data structures used extensively in computational geometry. (I favor the phrase "uniquely represented" over "strongly history independent" because unique representation is a slightly stronger condition -- unique representation implies strong-history independence, but the converse is false in some models of computation.)
   
   
4. Strongly History-Independent Hashing with Applications . With Guy Blelloch. FOCS 2007. BibTeX, [pdf slides], [slides handout]
   We build upon the work found in our earlier tech report, and develop a SHI perfect hash table, SHI ordered dictionaries, and a SHI order-maintenance data structure. We also improve the SHI hash table by incorporating a recent result of Pagh, Pagh, and Ruzic to show that 5-wise independence is good enough to yield expected constant time operations.
   Strongly History Independent Hashing with Deletion . With Guy Blelloch. Tech Report CMU-CS-06-156. BibTeX
   We present a strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. A hash table that supports deletions is SHI if it has a canonical memory representation up to randomness. Thus, the memory representation of a SHI hash table reveals exactly the information available through the hash table interface, and nothing more. We also give a general technique for efficiently implementing a host of SHI data structures on a RAM.
   
   
5. Combining Multiple Heuristics Online . With Matthew Streeter and Stephen F. Smith. AAAI 2007. BibTeX
   Given several different heuristics for some difficult problem, each of which may take advantage of different instance features, can you construct a single solver that exploits the strengths of each? We investigate this problem, and present black-box techniques for learning how to interleave the execution of multiple heuristics in order to improve average-case running time when given a sequence of problems to solve.
   
   
6. Restart Schedules for Ensembles of Problem Instances . With Matthew Streeter and Stephen F. Smith. AAAI 2007. BibTeX
   Given a randomized heuristic for some difficult problem, one can often significantly reduce the expected running time by periodically restarting the heuristic with a fresh random seed. We investigate the problem of selecting the best possible restart schedule for a set of instances, and then adapt the algorithms obtained to the online setting.
   
   
7. Combining Multiple Constraint Solvers: Results on the CPAI '06 Competition Data . With Matthew Streeter and Stephen F. Smith. Invited Paper, 2nd International CSP Solver Competition. BibTeX
   (Download the full proceedings [PDF]).
   In this paper we experimentally evaluate algorithms from our paper "Combining Multiple Heuristics Online," and show that our approach yields notable improvements in practice.
   
   
8. Stochastic Packing-Market Planning . EC 2007. BibTeX, [pdf slides]
   Motivated by the problem of centralized market clearing in a market with probabilistic supply and demand, we introduce the Stochastic Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set Packing problem. We provide an approximation algorithm for SPMP, and also give a linear programming based approximation for the expected weight of a maximum set packing in a random subhypergraph of a fixed hypergraph G, using techniques which may be of independent interest.
   
   
9. Quorum Placement in Networks: Minimizing Network Congestion . With Anupam Gupta, Bruce M. Maggs, Florian Oprea, and Michael K. Reiter. PODC 2006. BibTeX
   Quorum systems provide a logical framework for maintaining data consistency under distributed accesses in a distributed system and have several applications. Implementing a quorum system requires one to map the quorum system onto the physical network that comprises the distributed system by assigning the logical elements of the quorum system to machines. We call this task quorum placement, and develop algorithms for placing quorum systems to minimize the induced network congestion.
   
   
10. Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems,. With Vineet Goyal and R. Ravi. STACS 2006. BibTeX
    Demand-robust versions of common optimization problems were recently introduced (Dhamdhere et al., FOCS 2005) motivated by worst-case considerations of two-stage stochastic optimization models. We develop new techniques for demand-robust problems, and apply these techniques to demand-robust min-cut (improving the approximation factor from O(log(n)) to (1+\sqrt{2})), demand-robust shortest path (improving the approximation factor from 16 to 7.1), and some generalizations of these problems.
    
    
11. Approximating the k-Multicut Problem,. With Viswanath Nagarajan and Mohit Singh. SODA 2006. BibTeX
    We study the k-multicut problem: Given an edge weighted undirected graph, a set of L pairs of vertices, and a target number k less than or equal to L, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the multicut problem, where k = L. We obtain an 8/3+epsilon factor approximation for tree instances, for arbitrarily small positive epsilon and an O(log^2(n) log log (n)) approximation on general graphs, as well as a bicriteria solution that separates at least (1-epsilon)*k pairs at cost at most (2+epsilon)*OPT, where OPT is the optimal cost of separating k pairs.
    
    
12. Max-Min Fair Allocation of Indivisible Goods, Tech Report CMU-CS-05-144. BibTeX
    We consider the problem of fairly allocating a set of m indivisible goods to n agents, given the agents' utilities for each good. Fair allocations in this context are those maximizing the minimum utility received by any agent. We give hardness results and polynomial time approximation algorithms for several variants of this problem. Our main result is a bicriteria approximation in the model with additive utilities, in which a (1 − 1⁄k) fraction of the agents receive utility at least OPT/k, for any integer k.
    
    
13. A Model for Optimal Path Planning for Self-Reconfigurable Robots, ICAR 2003.
    Modular, self-reconfigurable robots may have many means of locomotion, each suitable for different types of terrain. Given costs for each means of locomotion as a function of the terrain's local characteristics (e.g. slope, unevenness), and costs for the reconfigurations needed to switch between two means of locomotion, we seek to minimize the cost of the robot's path to its goal. In this paper, we focus on practical algorithms that are parallelizable, and hence suitable for distributed computing platforms common to modular self-reconfigurable robots such as the PARC PolyBot platform.
    
    

Coauthors

Copyright Notices

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Copyright for STACS submissions is held by Springer-Verlag. These submissions can also be found via the LNCS series homepage