Shuchi's paper abstracts
Copyright notice
Papers by year
Shuchi's homepage
Approx Algorithms
Game Theory
Database Privacy
Online Algorithms
Networking
Machine Learning
UW CS
Theory Group
Theory Seminar
- Packing Multiway Cuts in Capacitated Graphs. [pdf]
With Siddharth Barman, to appear in SODA'09, and UW-Madison CS technical report 1642, Aug 2008. Also see the full version here. - Single Source Stochastic Routing. [pdf]
With Tim Roughgarden, APPROX'06. - On the Hardness of Approximating Multicut and Sparsest-Cut. [pdf]
With Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D. Sivakumar, Computational Complexity (2006), 15(2): 94-114. Preliminary version appeared in CCC'05. - Embeddings of Negative-type Metrics and An Improved
Approximation to Generalized Sparsest Cut. [ps,pdf]
With Anupam Gupta and Harald Raecke, ACM Transactions on Algorithms, SODA 2005 Special Issue (2008), 4(2). Preliminary version appeared in SODA'05. - Approximation Algorithms for Deadline-TSP and Vehicle
Routing with Time-Windows. [ps,pdf]
With Nikhil Bansal, Avrim Blum and Adam Meyerson, STOC'04. - Approximation
Algorithms for Orienteering and Discounted-Reward TSP.
[ps,pdf]
With Avrim Blum, David Karger, Terran Lane, Adam Meyerson and Maria Minkoff, SIAM Journal on Computing (2007), 37(2): 653-670. Preliminary version appeared in FOCS'03. - Correlation
Clustering.
[ps,pdf,extended abstract]
With Nikhil Bansal and Avrim Blum, Machine Learning, Special Issue on Clustering (2004), 56(1-3): 89-113. Preliminary version appeared in FOCS'02. - Bertrand Competition in Networks. [pdf,extended abstract]
With Tim Roughgarden, SAGT'08. - Approximate Pricing via Virtual Valuations. [pdf,extended abstract]
With Jason Hartline and Bobby Kleinberg, EC'07. - Optimal Cost-sharing Mechanisms for Steiner Forest Problems. [pdf]
With Mukund Sundararajan and Tim Roughgarden, WINE'06. - Bayesian
Optimal No-deficit Mechanism Design.
[pdf]
With Jason Hartline, R. Ravi and Uday Rajan, WINE'06. - Worst-case Payoffs of a Location Game.
[ps,pdf]
With Uday Rajan, R. Ravi and Amitabh Sinha, Operations Research Letters (2006), 34: 499-507. Preliminary version appeared as a poster in EC'04.
Also see technical report here. CMU-CS-03-141, May 2003. - Profit
Maximizing Mechanisms for the Extended Multicasting Game.
[ps,pdf]
With David Kitchin, Uday Rajan, Ramamoorthi Ravi and Amitabh Sinha, poster session, EC'03.
Also see technical report here. CMU-CS-02-164, July 2002. - Mechanisms for Internet Routing: A Study. [html]
With Aditya Akella and Srini Seshan. CMU-CS-02-163, July 2002. - On the Utility of Privacy-Preserving Histograms. [ps, pdf]
With Cynthia Dwork, Frank McSherry and Kunal Talwar, UAI'05. - Towards Privacy in Public Databases. [pdf]
With Cynthia Dwork, Frank McSherry, Hoeteck Wee and Adam Smith, TCC'05. - Scheduling
for Flow Time with Admission Control, or, How to Manage your To-Do
List.
[ps,pdf]
With Nikhil Bansal, Avrim Blum and Kedar Dhamdhere, ESA'03. (A shorter version appeared in MAPSP'03.) - Online Oblivious Routing.
[ps,pdf]
With Nikhil Bansal, Avrim Blum and Adam Meyerson, SPAA'03. - Static
Optimality and Dynamic Search Optimality in Lists and
Trees.
[ps,pdf]
With Avrim Blum and Adam Kalai, Algorithmica, Special Issue on Online Algorithms (2003), 36: 249-260. Preliminary version appeared in SODA'02. - Scaling
Properties of the Internet Graph.
[ps,pdf,
extended
abstract]
With Aditya Akella, Arvind Kannan and Srinivasan Seshan, ACM SIGCOMM Computer Communication Review, Special Issue on Science of Network Design (July, 2004), 34(3): 43-56. Preliminary version appeared in PODC'03. - QoS based Scheduling for Incorporating Variable
Rate Coded Voice in BLUETOOTH.
[ps,pdf]
With Huzur Saran and Mitali Singh, ICC'01.
APPROXIMATION ALGORITHMS & HARDNESS OF APPROXIMATION
-
We consider the following "cut-packing" problem: given several multiway cut instances in a common graph, the goal is to find a cut for each instance such that no edge participates in too many of the cuts. Note that we are not interested in small cuts, rather in nearly edge-disjoint ones. We give the first constant factor approximation in general graphs via an interesting use of laminarity.
-
We consider a stochastic version of the single-source routing problem: our goal is to maximize the value obtained from routing calls in a capacitated network without knowing the exact bandwidth requirement for each call. Our algorithm uses minimal distributional information about the volume (bandwidth requirement) of each call, but obeys the capacity constraints in the network with probability 1.
-
We show that the Multicut, Sparsest Cut and Min-2CNF= Deletion
problems are hard to approximate, assuming the Unique Games conjecture
of Khot (2002). In particular, we obtain an arbitrarily large constant
factor approximation for these problems, and show that a
quantitatively stronger version of the conjecture implies a hardness
factor of Omega(log log n).
-
We show how to embed n-point negative-type metrics into
Euclidean space with distortion O(log^{3/4}n). This embedding result
in turn, implies an O(log^{3/4}k)-approximation algorithm for the
Sparsest Cut problem with non-uniform demands.
-
We consider the following variant of the TSP --- Each vertex in a given
graph has a time-window associated with it. The goal is to
visit as many vertices as possible within their time-windows. We give
an O(log^2 n) approximation for this problem, where n is the number of
vertices. For the case in which each vertex has only a deadline, we obtain an
O(log n) approximation.
-
We give the first approximation (a 4-approximation) for the
Orienteering problem, where the goal is to visit as many vertices in a
given graph, as possible, in a fixed amount of time. Motivated by
planning problems in AI, we also give a constant factor approximation
for the discounted-reward TSP where the reward present at
vertex decreases with time, and the goal is to collect the maximum
reward possible.
-
We introduce the notion of Correlation Clustering,
motivated by document clustering and coreference analysis. Here we are
given a graph on objects with each pair of objects classified as
similar or dissimilar. A candidate clustering incurs a penalty for
each similar pair separated and each dissimilar pair agglomerated by
it. We give constant factor approximations for this problem.
-
We study the cost of selfish pricing in a limited supply combinatorial
market with many sellers and many consumers. Each seller prices her
item(s) so as to maximize her profit, and each (combinatorial)
consumer buys the bundle of items that brings her the most
utility. Our goal is to understand how the structure of the market
(the demand distribution, the substitute-complement relationships
between items, etc.) influences the prices of anarchy and stability
for this game. We study the game in a network setting where the items
are bandwidths on different edges, sellers own edges, and consumers
are interested in buying paths between their sources and
destinations. We provide nearly-tight upper and lower bounds on the
prices of anarchy and stability --- these depend on the existence and
the number of monopolies in the network, as well as traffic
distribution.
-
We consider the unit-demand envy-free pricing problem in a Bayesian setting --- we want to determine prices for k items so as to maximize the revenue obtained from a buyer that is interested in buying a single item, and whose values for the items are distributed according to known independent distributions. We show a surprising connection between this problem and the Bayesian optimal mechanism design problem. Using the concept of virtual valuations invented by Myerson (1981), we give a constant factor polynomial-time approximation to this problem.
-
It is well-known that cost-sharing mechanisms cannot simultaneously achieve approximate efficiency and approximate budget balance. In recent work, Roughgarden and Sundararajan showed how this impossibility result can be overcome by redefining efficiency in terms of social cost, rather than social value, and proved that for several optimization problems well-known budget-balanced mechanisms also provide good approximations to social cost. We extend this work to Steiner forest mechanisms and also show a connection between cost sharing and online optimization.
-
We consider the problem of designing a profit-maximizing auction when
the distributions of buyers' bids are known. We prove that this
problem is NP-hard, but can be solved exactly or approximated in
special cases. Unfortunately, in some cases, the optimal auction makes
a loss with a small probability. We therefore also consider the
problem of designing the best auction that never makes a loss.
-
We consider the following Location game: Given a metric space
with a distribution of customers, two firms compete to place
stores, so as to maximize their market share. Firms place
stores sequentially, and customers buy the product from the nearest
store. We show that the firm that moves first has a natural
disadvantage in this game, but that the disadvantage is bounded by a
quantity that depends only on the metric space.
-
We consider the problem of maximizing the seller's profit in a
multicasting game. We develop a mechanism that approximates the
optimal profit to the seller, when the game is highly profitable.
-
We give randomized constructions of histograms on data arising from
spherical as well as hypercubic distributions. These constructions
have two good properties. First, they preserve privacy of the data
points, and second, they approximately preserve distances between
points, thereby allowing several applications such as computing MSTs,
and solving facility location problems on the dataset.
-
We initiate a theoretical study of the census problem: The
census collects a vast amount of personal information from
individuals. The goal is to modify this database of information, so as
to protect the privacy of the individuals, while preserving
macroscopic properties and statistics that apply to the whole
population. We develop a framework for describing and comparing the
privacy offered by different sanitization techniques, and give a
natural algorithm for constructing a histogram on the data that
preserves privacy with a high probability.
-
We consider the problem of scheduling jobs on a single machine with
preemptions, when the server is allowed to reject jobs at some
penalty, with the objective of minimizing the total flow time and
total idle time of jobs. We show that a simple algorithm that keeps
track of the flow time accrued by the system and rejects a job
whenever this exceeds a certain limit, achieves a competitive
ratio of 2 with respect to the optimal offline algorithm.
-
Oblivious routing is the problem of picking a routing between each
pair of nodes in a network, without the knowledge of the traffic or
demands between each pair, with the goal of minimizing the congestion
in the network. We consider an online version of this problem, where
the algorithm picks a new routing every day, based on its knowledge of
the traffic seen in the past. We present an algorithm that incurs a
cost at most (1+eps) times the cost of the best overall routing.
-
We provide an online algorithm for the list update problem, that
simultaneously achieves the best possible competitive ratios against
the best static as well as dynamic list update algorithms in
hindsight. For search trees, we make partial progress towards
resolving the dynamic optimality conjecture -- we give a
(computational inefficient) algorithm that is optimal in hindsight if
we ignore the cost of rotations.
-
We use a combination of analysis and simulations to show that if the
Internet continues evolving as a powerlaw graph, the worst-case
congestion in the network is likely to grow very fast -- as
Omega(n^{1+Theta(1)}).