Packing multiway cuts in capacitated graphs (2008)
Barman, Siddharth, Chawla, Shuchi
We consider the following "multiway cut packing" problem in undirected graphs: we are given a graph G=(V,E) and k commodities, each corresponding to a set of terminals located at different vertices...
Algorithmic Pricing via Virtual Valuations (2008)
Chawla, Shuchi, Hartline, Jason, Kleinberg, Robert
Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand....
On the Scaling of Congestion in the Internet Graph (2004)
Aditya Akella, Shuchi Chawla, Arvind Kannan, Srinivasan Seshan
As the Internet grows in size, it becomes crucial to understand how the speeds of links in the network must improve in order to sustain the pressure of new end-nodes being added each day. Although...
Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows (2004)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible...
Realistic Models for Selfish Routing in the Internet (2003)
Aditya Akella, Shuchi Chawla, Srinivasan Seshan
this paper, we study the price of anarchy in a more realistic model of the Internet. We assume that the agents are unsplittable TCP flows. TCP is the predominant model of transport in today's...
Online Oblivious Routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
We consider the following clustering problem: we have a complete graph on # vertices (items), where each edge ### ## is labeled either # or depending on whether # and # have been deemed to be similar...
Approximation Algorithms for Orienteering and (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
In this paper, wegive the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
Scheduling for Flow-Time with Admission Control (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere
We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total ow time and...
Minmax Payos of a Location Game (2003)
Shuchi Chawla, Uday Rajan, R. Ravi, Amitabh Sinha
We consider a two-player, sequential location game, with n stages. At each stage, players 1 and 2 choose locations from a feasible set in sequence. After all moves are made, consumers each purchase...
Profit Maximizing Mechanisms for the Extended Multicasting Game (2003)
Shuchi Chawla, David Kitchin, Uday Rajan, R. Ravi, Amitabh Sinha
We consider the design of multicast networks when both edges and nodes are selfish agents. Our objective is a budget-balanced, strategy-proof mechanism which selects the set of clients to receive...
Scaling Properties of the Internet Graph (2003)
Aditya Akella, Shuchi Chawla, Arvind Kannan, Srinivasan Seshan
As the Internet grows in size, it becomes crucial to understand how the speeds of links in the network must improve in order to sustain the pressure of new end-nodes being added each day. Although...
Scaling Properties of the Internet Graph (2003)
Aditya Akella, Shuchi Chawla, Arvind Kannan, Srinivasan Seshan
As the Internet grows in size, it becomes crucial to understand how the speeds of links in the network must improve in order to sustain the pressure of new end-nodes being added each day. Although...
Online Oblivious Routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic...
Approximation Algorithms for Orienteering and Discounted-Reward TSP (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
Mechanisms for Coalition Formation and Cost Sharing in (2003)
Cuihong Li, Shuchi Chawla, Uday Rajan, Katia Sycara
In this paper we study the mechanism design problem of coalition formation and cost sharing in an electronic marketplace, where buyers can form coalitions to take advantage of discounts based on...
Approximation Algorithms for Orienteering and Discounted-Reward TSP (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Adam Meyerson, Maria Minko
In this paper, we give the rst constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2002)
Avrim Blum, Shuchi Chawla, Adam Kalai
Adaptive data structures form a central topic of online algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u; v) is labeled either + or depending on whether u and v have been deemed to be similar...
Mechanisms for Internet Routing: A Study (2002)
Aditya Akella, Shuchi Chawla, Srini Seshan
In this paper, we address the issue of Routing in the Internet from a Game Theoretic perspective. We adopt a two-pronged strategy: rstly, we revisit two `classic' models of the Nash equilibria of a...
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2001)
Avrim Blum, Shuchi Chawla, Adam Kalai
Adaptive data structures form a central topic of online algorithms research, beginning with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and...
Learning from Labeled and Unlabeled Data using Graph Mincuts (2001)
Many application domains suffer from not having enough labeled training data for learning. However, large...
Thesis (M.S. in Electrical Engineering)--Vanderbilt University, 1991.