Arrow Research search

Author name cluster

Amit Kumar 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

40 papers
1 author row

Possible papers

40

ICML Conference 2024 Conference Paper

Centralized Selection with Preferences in the Presence of Biases

  • L. Elisa Celis
  • Amit Kumar 0001
  • Nisheeth K. Vishnoi
  • Andrew Xu

This paper considers the scenario in which there are multiple institutions, each with a limited capacity for candidates, and candidates, each with preferences over the institutions. A central entity evaluates the utility of each candidate to the institutions, and the goal is to select candidates for each institution in a way that maximizes utility while also considering the candidates’ preferences. The paper focuses on the setting in which candidates are divided into multiple groups and the observed utilities of candidates in some groups are biased–systematically lower than their true utilities. The first result is that, in these biased settings, prior algorithms can lead to selections with sub-optimal true utility and significant discrepancies in the fraction of candidates from each group that get their preferred choices. Subsequently, an algorithm is presented along with proof that it produces selections that achieve near-optimal group fairness with respect to preferences while also nearly maximizing the true utility under distributional assumptions. Further, extensive empirical validation of these results in real-world and synthetic settings, in which the distributional assumptions may not hold, are presented.

Details

SODA Conference 2022 Conference Paper

How many Clusters? - An algorithmic answer

  • Chiranjib Bhattacharyya
  • Ravindran Kannan
  • Amit Kumar 0001

Many algorithms for clustering high dimensional data assume that k, the number of clusters, is given. However, there has been little work on provably inferring k from the data. This paper gives polynomial time algorithms for finding k from the data assuming it satisfies certain natural deterministic conditions. Informally, we assume that there is a Ground Truth (GT) clustering of the data with the following properties: (i) Each cluster has a certain minimum size, (ii) the inter-mean separation of any two distinct clusters in the GT is large enough (although still weaker than what is typically assumed in the literature), and (iii) we define a novel “no large sub-cluster” (NLSC) property that characterizes the notion of a cluster by stipulating that there be no subsets of low “directional variance”. NLSC is indeed satisfied by large class of distributions including log-concave densities. The first major contribution is an algorithm for finding k where m, the minimum GT cluster size, is assumed to be known. This algorithm uses a novel rounding procedure which finds subsets of size m with low Directional Variance by rounding a SDP relaxation using Cheeger's inequality and it is shown that k is precisely the number of such sets whose means are well-separated. The harder problem of finding k when m not given is addressed by running the previous algorithm for each value of m to find candidate values of k and the corresponding k -clustering. The second major contribution of this paper is a test which certifies the correct candidate thereby yielding a polynomial time algorithm which finds k.

Details

ICML Conference 2022 Conference Paper

Online Algorithms with Multiple Predictions

  • Keerti Anand
  • Rong Ge 0001
  • Amit Kumar 0001
  • Debmalya Panigrahi

This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.

Details

SODA Conference 2022 Conference Paper

Online Discrepancy with Recourse for Vectors and Graphs

  • Anupam Gupta 0001
  • Vijaykrishna Gurunathan
  • Ravishankar Krishnaswamy
  • Amit Kumar 0001
  • Sahil Singla 0001

The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in [–1, 1] n, find a signing σ ( a ) ∊ {±1} of each vector a to minimize the discrepancy ‖ Σ a σ ( a ) · a ‖ ∞. This problem has been extensively studied in the static/offline setting. In this paper we initiate its study in the fully-dynamic setting with recourse: the algorithm sees a stream of T insertions and deletions of vectors, and at each time must maintain a low-discrepancy signing, while also minimizing the amortized recourse (the number of times any vector changes its sign) per update. For general vectors, we show algorithms which almost match Spencer's offline discrepancy bound, with O(n polylog T ) amortized recourse per update. The crucial idea behind our algorithm is to compute a basic feasible solution to the linear relaxation in a distributed and recursive manner, which helps find a low-discrepancy signing. We bound the recourse using the distributed computation of the basic solution, and argue that only a small part of the instance needs to be re-computed at each update. Since vector balancing has also been greatly studied for sparse vectors, we then give algorithms for low-discrepancy edge orientation, where we dynamically maintain signings for 2-sparse vectors in an n -dimensional space. Alternatively, this can be seen as orienting a dynamic set of edges of an n -vertex graph to minimize the discrepancy, i. e. , the absolute difference between in- and out-degrees at any vertex. We present a deterministic algorithm with O (polylog n ) discrepancy and O (polylog n ) amortized recourse. The core ideas are to dynamically maintain an expander-decomposition with low recourse (using a very simple approach), and then to show that, as the expanders change over time, a natural local-search algorithm converges quickly (i. e. , with low recourse) to a low-discrepancy solution. We also give strong lower bounds (with some matching upper bounds) for local-search discrepancy minimization algorithms for vector balancing and edge orientation.

Details

FOCS Conference 2021 Conference Paper

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Debmalya Panigrahi

We study the $k$ -server problem with time-windows. In this problem, each request $i$ arrives at some point $v_{i}$ of an $n$ -point metric space at time $b_{i}$ and comes with a deadline $e_{i}$. One of the $k$ servers must be moved to $v_{i}$ at some time in the interval [ $b_{i}, e_{i}$ ] to satisfy this request. We give an online algorithm for this problem with a competitive ratio of $\text{poly}\log(n, \Delta)$, where $\Delta$ is the aspect ratio of the metric space. Prior to our work, the best competitive ratio known for this problem was $O(k\ \text{poly}\log(n))$ given by Azar et al. (STOC 2017). Our algorithm is based on a new covering linear program relaxation for $k$ -server on HSTs. This LP naturally corresponds to the min-cost flow formulation of $k$ -server, and easily extends to the case of time-windows. We give an online algorithm for obtaining a feasible fractional solution for this LP, and a primal dual analysis framework for accounting the cost of the solution. Together, they yield a new $k$ -server algorithm with poly-logarithmic competitive ratio, and extend to the time-windows case as well. Our principal technical contribution lies in thinking of the covering LP as yielding a truncated covering LP at each internal node of the tree, which allows us to keep account of server movements across subtrees. We hope that this LP relaxation and the algorithm/analysis will be a useful tool for addressing $k$ -server and related problems.

Details

ICML Conference 2021 Conference Paper

Finding k in Latent k- polytope

  • Chiranjib Bhattacharyya
  • Ravindran Kannan
  • Amit Kumar 0001

The recently introduced Latent $k-$ Polytope($\LkP$) encompasses several stochastic Mixed Membership models including Topic Models. The problem of finding $k$, the number of extreme points of $\LkP$, is a fundamental challenge and includes several important open problems such as determination of number of components in Ad-mixtures. This paper addresses this challenge by introducing Interpolative Convex Rank(\INR) of a matrix defined as the minimum number of its columns whose convex hull is within Hausdorff distance $\varepsilon$ of the convex hull of all columns. The first important contribution of this paper is to show that under \emph{standard assumptions} $k$ equals the \INR of a \emph{subset smoothed data matrix} defined from Data generated from an $\LkP$. The second important contribution of the paper is a polynomial time algorithm for finding $k$ under standard assumptions. An immediate corollary is the first polynomial time algorithm for finding the \emph{inner dimension} in Non-negative matrix factorisation(NMF) with assumptions which are qualitatively different than existing ones such as \emph{Separability}. %An immediate corollary is the first polynomial time algorithm for finding the \emph{inner dimension} in Non-negative matrix factorisation(NMF) with assumptions considerably weaker than \emph{Separability}.

Details

SODA Conference 2021 Conference Paper

Hardness of Approximation for Orienteering with Multiple Time Windows

  • Naveen Garg 0001
  • Sanjeev Khanna
  • Amit Kumar 0001

Vehicle routing problems are a broad class of combinatorial optimization problems that can be formulated as the problem of finding a tour in a weighted graph that optimizes some function of the visited vertices. For instance, a canonical and extensively studied vehicle routing problem is the orienteering problem where the goal is to find a tour that maximizes the number of vertices visited by a given deadline. In this paper, we consider the computational tractability of a well-known generalization of the orienteering problem called the Orient-MTW problem. The input to Orient-MTW consists of a weighted graph G ( V, E ) where for each vertex v ∊ V we are given a set of time instants T v ⊆ [ T ], and a source vertex s. A tour starting at s is said to visit a vertex v if it transits through v at any time in the set T v. The goal is to find a tour starting at the source vertex that maximizes the number of vertices visited. It is known that this problem admits a quasi-polynomial time O (log OPT)-approximation ratio where OPT is the optimal solution value but until now no hardness better than an APX-hardness was known for this problem. Our main result is an -hardness for this problem that holds even when the underlying graph G is an undirected tree. This is the first super-constant hardness result for the Orient-MTW problem. The starting point for our result is the hardness of the SetCover problem which is known to hold on instances with a special structure. We exploit this special structure of the hard SetCover instances to first obtain a new proof of the APX-hardness result for Orient-MTW that holds even on trees of depth 2. We then recursively amplify this constant factor hardness to an -hardness, while keeping the resulting topology to be a tree. Our amplified hardness proof crucially utilizes a delicate concavity property which shows that in our encoding of SetCover instances as instances of the Orient-MTW problem, whenever the optimal cost for SetCover instance is large, any tour, no matter how it allocates its time across different sub-trees, can not visit too many vertices overall. We believe that this reduction template may also prove useful in showing hardness of other vehicle routing problems.

Details

STOC Conference 2020 Conference Paper

Caching with time windows

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Debmalya Panigrahi

We consider the (weighted) Paging with Time Windows problem, which is identical to the classical weighted paging problem but where each page request only needs to be served by a given deadline. This problem arises in many practical applications of online caching, such as the deadline I/O scheduler in the Linux kernel and video-on-demand streaming. From a theoretical perspective, this generalizes the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithms (e.g., Emek et al. STOC '16, Azar et al. STOC '17, Azar and Touitou FOCS '19, etc.).

Details

SODA Conference 2019 Conference Paper

Elastic Caching

  • Anupam Gupta 0001
  • Ravishankar Krishnaswamy
  • Amit Kumar 0001
  • Debmalya Panigrahi
Details

FOCS Conference 2018 Conference Paper

Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time

  • Jatin Batra
  • Naveen Garg 0001
  • Amit Kumar 0001

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement p_j, release date r_j and weight w_j. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudo-polynomial time constant approximation algorithm for this problem. The algorithm also extends directly to the problem of minimizing the _p norm of weighted flow-times. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multi-cut problem on trees, which we call Demand MultiCut problem. Even though we do not give a constant factor approximation algorithm for the Demand MultiCut problem on trees, we show that the specific instances of Demand MultiCut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of DP table.

Details

STOC Conference 2017 Conference Paper

Online and dynamic algorithms for set cover

  • Anupam Gupta 0001
  • Ravishankar Krishnaswamy
  • Amit Kumar 0001
  • Debmalya Panigrahi

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offline algorithms for set cover. The former leads to a competitive ratio of O (log n t ), where n t is the number of currently active elements at timestep t , while the latter yields competitive ratios dependent on f t , the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

Details

SODA Conference 2015 Conference Paper

Rejecting jobs to Minimize Load and Maximum Flow-time

  • Anamitra Roy Choudhury
  • Syamantak Das
  • Naveen Garg 0001
  • Amit Kumar 0001

Online algorithms are usually analyzed using the notion of competitive ratio which compares the solution obtained by the algorithm to that obtained by an online adversary for the worst possible input sequence. Often this measure turns out to be too pessimistic, and one popular approach especially for scheduling problems has been that of “resource augmentation” which was first proposed by Kalyanasundaram and Pruhs. Although resource augmentation has been very successful in dealing with a variety of objective functions, there are problems for which even a (arbitrary) constant speedup cannot lead to a constant competitive algorithm. In this paper we propose a “rejection model” which requires no resource augmentation but which permits the online algorithm to not serve an epsilon-fraction of the requests. The problems considered in this paper are in the restricted assignment setting where each job can be assigned only to a subset of machines. For the load balancing problem where the objective is to minimize the maximum load on any machine, we give O (log 2 l/ε)-competitive algorithm which rejects at most an ε-fraction of the jobs. For the problem of minimizing the maximum weighted flow-time, we give an O (1/ε 4 )-competitive algorithm which can reject at most an ε-fraction of the jobs by weight. We also extend this result to a more general setting where the weights of a job for measuring its weighted flow-time and its contribution towards total allowed rejection weight are different. This is useful, for instance, when we consider the objective of minimizing the maximum stretch. We obtain an O (1/ε 6 )-competitive algorithm in this case. Our algorithms are immediate dispatch, though they may not be immediate reject. All these problems have strong lower bounds in speed augmentation model.

Details

SODA Conference 2014 Conference Paper

Maintaining Assignments Online: Matching, Scheduling, and Flows

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Cliff Stein 0001

Consider the following edge-orientation problem: edges of a graph appear online one-by-one and they to be directed—given an “orientation”. We want to ensure that the in-degree of each vertex remains low. (This is a simple case of scheduling unit-sized jobs on machines, where each job can only go on one of two machines.) If the edge-orientations we assign are irrevocable, we suffer a significant loss in quality due to online decision-making (as compared to the offline performance). For instance the best online competitive ratio achievable is Θ(log m ) for even this toy problem. But what if the decisions are not irrevocable — what if we allow a limited number of reassignments? Can we do much better? We show that indeed we can. For instance, for edge-orientation, we can achieve a constant-competitive load while doing only a constant number of re-orientations per edge (in an amortized sense). For more substantial problems, our results are as follows: For online matching, where the left vertices arrive online and must be matched to the right vertices, we give an algorithm that reassigns the left vertices an (amortized) constant number of times, and maintains a constant factor to the optimal load on the right vertices. We extend this to restricted machine scheduling with arbitrary sized jobs and give an algorithm that maintains load which is O (log log mn ) times the optimum, and reassigns each job only an (amortized) constant number of times. Consider a digraph with a single source, where sinks arrive online and want to send unit flow to the source. The goal is to minimize the congestion on the edges. Suppose there is an offline flow such that the total length of the flow paths is F *. We give an algorithm that reroutes flow along O ( F * ) edges and achieves a O (1)-approximation to the congestion.

Details

SODA Conference 2014 Conference Paper

Online Steiner Tree with Deletions

  • Anupam Gupta 0001
  • Amit Kumar 0001

In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of Θ(log n ) on the competitiveness has been known for two decades. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can still maintain a constant-competitive tree online. But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman ( SIAM J. Disc. Math, 4(3): 369–384, 1991 ) had also considered this model, and it gave an algorithm that made at most O ( n 3/2 ) edge changes for the first n requests, and maintained a constant-competitive tree online. In this paper we improve on these results:

Details

STOC Conference 2013 Conference Paper

The power of deferral: maintaining a constant-competitive steiner tree online

  • Albert Gu
  • Anupam Gupta 0001
  • Amit Kumar 0001

In the online Steiner tree problem, a sequence of points is revealed one-by-one: when a point arrives, we only have time to add a single edge connecting this point to the previous ones, and we want to minimize the total length of edges added. Here, a tight bound has been known for two decades: the greedy algorithm maintains a tree whose cost is O(log n) times the Steiner tree cost, and this is best possible. But suppose, in addition to the new edge we add, we have time to change a single edge from the previous set of edges: can we do much better? Can we, e.g., maintain a tree that is constant-competitive?

Details

SODA Conference 2012 Conference Paper

Constant factor approximation algorithm for the knapsack median problem

  • Amit Kumar 0001

We give a constant factor approximation algorithm for the following generalization of the k -median problem. We are given a set of clients and facilities in a metric space. Each facility has a facility opening cost, and we are also given a budget B. The objective is to open a subset of facilities of total cost at most B, and minimize the total connection cost of the clients. This settles an open problem of Krishnaswamy-Kumar-Nagarajan-Sabharwal-Saha. The natural linear programming relaxation for this problem has unbounded integrality gap. Our algorithm strengthens this relaxation by adding constraints which stipulate which facilities a client can get assigned to. We show that after suitably modifying a fractional solution, one can get rich structural properties which allow us to get the desired approximation ratio.

Details

SODA Conference 2012 Conference Paper

Resource augmentation for weighted flow-time explained by dual fitting

  • S. Anand 0002
  • Naveen Garg 0001
  • Amit Kumar 0001

We propose a general dual-fitting technique for analyzing online scheduling algorithms in the unrelated machines setting where the objective function involves weighted flow-time, and we allow the machines of the on-line algorithm to have (1 + ε)-extra speed than the offline optimum (the so-called speed augmentation model). Typically, such algorithms are analyzed using non-trivial potential functions which yield little insight into the proof technique. We propose that one can often analyze such algorithms by looking at the dual (or Lagrangian dual) of the linear (or convex) program for the corresponding scheduling problem, and finding a feasible dual solution as the on-line algorithm proceeds. As representative cases, we get the following results: For the problem of minimizing weighted flow-time, we give an O (1/ε)-competitive greedy algorithm. This is an improvement by a factor of 1/ε on the competitive ratio of the greedy algorithm of Chadha-Garg-Kumar-Muralidhara. For the problem of minimizing weighted ℓ k norm of flow-time, we show that a greedy algorithm gives an -competitive ratio. This marginally improves the result of Im and Moseley. For the problem of minimizing weighted flow-time plus energy, and when the energy function f ( s ) is equal to s γ, γ > 1, we show that a natural greedy algorithm is O (γ 2 )-competitive. Prior to our work, such a result was known for the related machines setting only (Gupta-Krishnaswamy-Pruhs).

Details

SODA Conference 2011 Conference Paper

The Matroid Median Problem

  • Ravishankar Krishnaswamy
  • Amit Kumar 0001
  • Viswanath Nagarajan
  • Yogish Sabharwal
  • Barna Saha

In the classical k -median problem, we are given a metric space and would like to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper, we consider the following generalization of the problem: instead of opening at most k centers, what if each center belongs to one of T different types, and we are allowed to open at most k i centers of type i (for each i = 1, 2, …, T ). The case T = 1 is the classical k -median, and the case of T = 2 is the red-blue median problem for which Hajiaghayi et al. [ESA 2010] recently gave a constant-factor approximation algorithm. Even more generally, what if the set of open centers had to form an independent set from a matroid? In this paper, we give a constant factor approximation algorithm for such matroid median problems. Our algorithm is based on rounding a natural LP relaxation in two stages: in the first step, we sparsify the structure of the fractional solution while increasing the objective function value by only a constant factor. This enables us to write another LP in the second phase, for which the sparsified LP solution is feasible. We then show that this second phase LP is in fact integral; the integrality proof is based on a connection to matroid intersection. We also consider the penalty version (alternately, the so-called prize collecting version) of the matroid median problem and obtain a constant factor approximation algorithm for it. Finally, we look at the Knapsack Median problem (in which the facilities have costs and the set of open facilities need to fit into a Knapsack) and get a bicriteria approximation algorithm which violates the Knapsack bound by a small additive amount.

Details

FOCS Conference 2010 Conference Paper

Clustering with Spectral Norm and the k-Means Algorithm

  • Amit Kumar 0001
  • Ravindran Kannan

There has been much progress on efficient algorithms for clustering data points generated by a mixture of k probability distributions under the assumption that the means of the distributions are well-separated, i. e. , the distance between the means of any two distributions is at least Ω(k) standard deviations. These results generally make heavy use of the generative model and particular properties of the distributions. In this paper, we show that a simple clustering algorithm works without assuming any generative (probabilistic) model. Our only assumption is what we call a "proximity condition'': the projection of any data point onto the line joining its cluster center to any other cluster center is Ω(k) standard deviations closer to its own center than the other center. Here the notion of standard deviations is based on the spectral norm of the matrix whose rows represent the difference between a point and the mean of the cluster to which it belongs. We show that in the generative models studied, our proximity condition is satisfied and so we are able to derive most known results for generative models as corollaries of our main result. We also prove some new results for generative models - e. g. , we can cluster all but a small fraction of points only assuming a bound on the variance. Our algorithm relies on the well known k-means algorithm, and along the way, we prove a result of independent interest - that the k-means algorithm converges to the "true centers'' even in the presence of spurious points provided the initial (estimated) centers are close enough to the corresponding actual centers and all but a small fraction of the points satisfy the proximity condition. Finally, we present a new technique for boosting the ratio of inter-center separation to standard deviation. This allows us to prove results for learning certain mixture of distributions under weaker separation conditions.

Details

STOC Conference 2009 Conference Paper

A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation

  • Jivitej S. Chadha
  • Naveen Garg 0001
  • Amit Kumar 0001
  • V. N. Muralidhara

We consider the online problem of scheduling jobs on unrelated machines so as to minimize the total weighted flow time. This problem has an unbounded competitive ratio even for very restricted settings. In this paper we show that if we allow the machines of the online algorithm to have ε more speed than those of the offline algorithm then we can get an O((1+ε -1 ) 2 )-competitive algorithm. Our algorithm schedules jobs preemptively but without migration. However, we compare our solution to an offline algorithm which allows migration. Our analysis uses a potential function argument which can also be extended to give a simpler and better proof of the randomized immediate dispatch algorithm of Chekuri-Goel-Khanna-Kumar for minimizing average flow time on parallel machines.

Details

FOCS Conference 2007 Conference Paper

Minimizing Average Flow-time: Upper and Lower Bounds

  • Naveen Garg 0001
  • Amit Kumar 0001

We consider the problem of minimizing average flow time on multiple machines when each job can be assigned only to a specified subset of the machines. This is a special case of scheduling on unrelated machines and we show that no online algorithm can have a bounded competitive ratio. We provide an O(log P)-approximation algorithm by modifying the single-source unsplittable flow algorithm of Dinitz, et. al. Here P is the ratio of the maximum to the minimum processing times. We establish an Omega(log P)-integrality gap for our LP-relaxation and use this to show an Omega(log P/log log P) lower bound on the approximability of the problem. We then extend the hardness results to the problem of minimizing flow time on parallel machines and establish the first non-trivial lower bounds on the approximability; we show that the problem cannot be approximated to within Omega(radiclog P/log log P).

Details

STOC Conference 2006 Conference Paper

Minimizing average flow time on related machines

  • Naveen Garg 0001
  • Amit Kumar 0001

We give the first on-line poly-logarithmic competitve algorithm for minimizing average flow time with preemption on related machines, i.e., when machines can have different speeds. This also yields the first poly-logarithmic polynomial time approximation algorithm for this problem.More specifically, we give an O(log 2 P • log S)-competitive algorithm, where P is the ratio of the biggest and the smallest processing time of a job, and S is the ratio of the highest and the smallest speed of a machine. Our algorithm also has the nice property that it is non-migratory. The scheduling algorithm is based on the concept of making jobs wait for a long enough time before scheduling them on slow machines.

Details

STOC Conference 2004 Conference Paper

Multi-processor scheduling to minimize flow time with epsilon resource augmentation

  • Chandra Chekuri
  • Ashish Goel
  • Sanjeev Khanna
  • Amit Kumar 0001

We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their L p norms, for any fixed p ≥ 1.

Details

FOCS Conference 2003 Conference Paper

Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Martin Pál
  • Tim Roughgarden

We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. The first constant-factor approximation algorithm for this problem was recently given by Kumar et al. ; however, this algorithm and its analysis are both quite complicated, and its performance guarantee is extremely large. In this paper, we give a conceptually simple 12-approximation algorithm for this problem. Our analysis of this algorithm makes crucial use of cost sharing, the task of allocating the cost of an object to many users of the object in a "fair" manner. While techniques from approximation algorithms have recently yielded new progress on cost sharing problems, our work is the first to show the converse - those ideas from cost sharing can be fruitfully applied in the design and analysis of approximation algorithms.

Details

STOC Conference 2003 Conference Paper

Simpler and better approximation algorithms for network design

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Tim Roughgarden

We give simple and easy-to-analyze randomized approximation algorithms for several well-studied NP-hard network design problems. Our algorithms improve over the previously best known approximation ratios. Our main results are the following. We give a randomized 3.55-approximation algorithm for the connected facility location problem. The algorithm requires three lines to state, one page to analyze, and improves the best-known performance guarantee for the problem. We give a 5.55-approximation algorithm for virtual private network design . Previously, constant-factor approximation algorithms were known only for special cases of this problem. We give a simple constant-factor approximation algorithm for the single-sink buy-at-bulk network design problem. Our performance guarantee improves over what was previously known, and is an order of magnitude improvement over previous combinatorial approximation algorithms for the problem.

Details

FOCS Conference 2002 Conference Paper

A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

  • Amit Kumar 0001
  • Anupam Gupta 0001
  • Tim Roughgarden

We present the first constant factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge. Capacity can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem. Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or of metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.

Details

STOC Conference 2001 Conference Paper

Provisioning a virtual private network: a network design problem for multicommodity flow

  • Anupam Gupta 0001
  • Jon M. Kleinberg
  • Amit Kumar 0001
  • Rajeev Rastogi
  • Bülent Yener

Consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. Virtual private networks (VPNs) are services that support such a construct; rather than building a new physical network on the group of nodes that must be connected, bandwidth in the underlying network is reserved for communication within the group, forming a virtual “sub-network.”

Details

FOCS Conference 2001 Conference Paper

Sorting and Selection with Structured Costs

  • Anupam Gupta 0001
  • Amit Kumar 0001

The study of the effect of priced information on basic algorithmic problems was initiated by M. Charikar et al. (2000). The authors continue the study of sorting and selection in the priced comparison model, i. e. , when each comparison has an associated cost, and answer some of the open problems suggested by Charikar et al. If the comparison costs are allowed to be arbitrary, we show that one cannot get good approximation ratios. A different way to assign costs is based on the idea that one can distill out an intrinsic value for each item being compared, such that the cost of comparing two elements is some "well-behaved" or "structured" function of their values. We feel that most practical applications will have some structured cost property. The authors study the problems of sorting and selection (which includes finding the maximum and the median) in the structured cost model. We get a variety of approximation results for these problems, depending on the restrictions we put on the structured costs. We show that it is possible to get much improved results with the structured cost model than the case when we do not have any assumptions on comparison costs.

Details

FOCS Conference 2001 Conference Paper

Traveling with a Pez Dispenser (Or, Routing Issues in MPLS)

  • Anupam Gupta 0001
  • Amit Kumar 0001
  • Rajeev Rastogi

MultiProtocol Label Switching (MPLS) is a routing model proposed by the IETF for the Internet, and is becoming widely popular. In this paper, we initiate a theoretical study of the routing model, and give routing algorithms and lower bounds in a variety of situations. We first study the routing problems on the line. We then build up our results from paths through trees to more general graphs. The basic technique to go to general graphs is that of finding a tree cover, which is a small set of subtrees of the graph such that for each pair of vertices, one of the trees contains a shortest (or near-shortest) path between them. The concept of tree covers appears to have many interesting applications.

Details

FOCS Conference 2000 Conference Paper

Fairness Measures for Resource Allocation

  • Amit Kumar 0001
  • Jon M. Kleinberg

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of "global" approximation guarantee, and we explore its consequences in a range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue-one not encountered in the traditional design of approximation algorithms-is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of basic problems in resource allocation, and on the structure of their feasible solutions.

Details
v2026.09.13