Khanna, Sanjeev
Email Address
ORCID
Disciplines
relationships.isProjectOf
relationships.isOrgUnitOf
Position
Introduction
Research Interests
Collection
58 results
Search Results
Now showing 1 - 10 of 58
Publication Algorithms for the Generalized Sorting Problem(2011-10-01) Kannan, Sampath; Huang, Zhiyi; Khanna, SanjeevWe study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pairwise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V,E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E' E of edges to probe such that the directed graph induced by E' contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n3⁄2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p2 , n3⁄2p √p}) comparisons suffice on average to sort.Publication Approximation Schemes for Preemptive Weighted Flow Time(2002-05-19) Chekuri, Chandra; Khanna, SanjeevWe present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a (1 + ε)- approximate solution for any instance of weighted flow time in O(nO(ln W ln P/ε3) time; here P is the ratio of maximum job processing time to minimum job processing time, and W is the ratio of maximum job weight to minimum job weight. This result directly gives a quasi-PTAS for weighted flow time when P and W are poly-bounded, and a PTAS when they are both O(1). We strengthen the former result to show that in order to get a quasi-PTAS it suffices to have just one of P and W to be poly-bounded. Our result provides strong evidence to the hypothesis that the weighted flow time problem has a PTAS. We note that the problem is strongly NP-hard even when P and W are O(1). We next consider two important special cases of weighted flow time, namely, when P is O(1) and W is arbitrary, and when the weight of a job is inverse of its processing time referred to as the stretch metric. For both of the above special cases we obtain a (1 + ε)-approximation for any ε > 0 by using a randomized partitioning scheme to reduce an arbitrary instance to several instances all of which have P and W bounded by a constant that depends only on ε.Publication On Broadcast Disk Paging(1999-03-13) Khanna, Sanjeev; Liberatore, VincenzoBroadcast disks are an emerging paradigm for massive data dissemination. In a broadcast disk, data is divided into n equal-sized pages, and pages are broadcast in a round-robin fashion by a server. Broadcast disks are effective because many clients can simultaneously retrieve any transmitted data. Paging is used by the clients to improve performance, much as in virtual memory systems. However, paging on broadcast disks differs from virtual memory paging in at least two fundamental aspects: - A page fault in the broadcast disk model has a variable cost that depends on the requested page as well as the current state of the broadcast. - Prefetching is both natural and a provably essential mechanism for achieving significantly better competitive ratios in broadcast disk paging. In this paper, we design a deterministic algorithm that uses prefetching to achieve an O(n log k) competitive ratio for the broadcast disk paging problem, where k denotes the size of the client's cache. We also show a matching lower bound of Ω(n log k) that applies even when the adversary is not allowed to use prefetching. In contrast, we show that when prefetching is not allowed, no deterministic online algorithm can achieve a competitive ratio better than Ω(nk). Moreover, we show a lower bound of Ω(n log k) on the competitive ratio achievable by any nonprefetching randomized algorithm against an oblivious adversary. These lower bounds are trivially matched from above by known results about deterministic and randomized marking algorithms for paging. An interpretation of our results is that in the broadcast disk paging, prefetching is a perfect substitute for randomization.Publication Reconstructing Strings from Random Traces(2004-01-11) Kannan, Sampath; Batu, Tugkan; Khanna, Sanjeev; McGregor, AndrewWe are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly reconstruct the string t from these observed traces. We initiate here a study of deletion rates for which we can successfully reconstruct the original string using a small number of samples. We investigate a simple reconstruction algorithm called Bitwise Majority Alignment that uses majority voting (with suitable shifts) to determine each bit of the original string. We show that for random strings t, we can reconstruct the original string (w.h.p.) for q = O(1/ log n) using only O(log n) samples. For arbitrary strings t, we show that a simple modification of Bitwise Majority Alignment reconstructs a string that has identical structure to the original string (w.h.p.) for q = O(1/n1/2+ε) using O(1) samples. In this case, using O(n log n) samples, we can reconstruct the original string exactly. Our setting can be viewed as the study of an idealized biological evolutionary process where the only possible mutations are random deletions. Our goal is to understand at what mutation rates, a small number of observed samples can be correctly aligned to reconstruct the parent string. In the process of establishing these results, we show that Bitwise Majority Alignment has an interesting selfcorrecting property whereby local distortions in the traces do not generate errors in the reconstruction and eventually get corrected.Publication A PTAS for Minimizing Average Weighted Completion Time With Release Dates on Uniformly Related Machines(2000-01-01) Chekuri, Chandra; Khanna, SanjeevA classical scheduling problem is to find schedules that minimize average weighted completion time of jobs with release dates. When multiple machines are available, the machine environments may range from identical machines (the processing time required by a job is invariant across the machines) at one end, to unrelated machines (the processing time required by a job on any machine is an arbitrary function of the specific machine) at the other end of the spectrum. While the problem is strongly NP-hard even in the case of a single machine, constant factor approximation algorithms have been known for even the most general machine environment of unrelated machines. Recently, a polynomial-time approximation scheme (PTAS) was discovered for the case of identical parallel machines [1]. In contrast, it is known that this problem is MAX SNP-hard for unrelated machines [10]. An important open problem is to determine the approximability of the intermediate case of uniformly related machines where each machine i has a speed si and it takes p/si time to executing a job of processing size pIn this paper, we resolve this problem by obtaining a PTAS for the problem. This improves the earlier known ratio of (2 + ∈) for the problem.Publication Algorithms for Minimizing Weighted Flow Time(2001-07-06) Chekuri, Chandra; Khanna, Sanjeev; Zhu, AnWe study the problem of minimizing weighted flow time on a single machine in the preemptive setting. We present an O(log2 P)-competitive semi-online algorithm where P is the ratio of the maximum and minimum processing times of jobs in the system. In the offline setting we show that a (2 + ε)-approximation is achievable in quasi-polynomial time. These are the first non-trivial results for the weighted versions of minimizing flow time. For multiple machines we show that no competitive randomized online algorithm exists for weighted flow time. We also present an improved online algorithm for minimizing total stretch (a special case of weighted flow time) on multiple machines.Publication A Deterministic Algorithm for the COST-DISTANCE Problem(2001-01-07) Chekuri, Chandra; Khanna, Sanjeev; Naor, JosephThe COST-DISTANCE network design problem is the following. We are given an undirected graph G = (V,E), a designated root vertex r ∈ V, and a set of terminals S ⊂ of V. We are also given two non-negative real valued functions defined on E, namely, a cost function c and a length function l, and a non-negative weight function w on the set S. The goal is to find a tree T that connects the terminals in S to the root r and minimizes σ e ∈ Tc(e) + σ t ∈ Sw(t)lT(r,t), where lT(r,t) is the length of the path in T from t to r. We give a deterministic O(log k) approximation algorithm for the COST-DISTANCE network design problem, in a sense derandomizing the algorithm given in [4]. Our algorithm is based on a natural linear programming relaxation of the problem and in the process we show that its integrality gap is O(log k).Publication Approximation Algorithms for Data Placement on Parallel Disks(2000-01-01) Golubchik, L.; Khanna, Sanjeev; Khuller, S.; Thurimella, R.; Zhu, AnWe study an optimization problem that arises in the context of data placement in multimedia storage systems. We are given a collection of M multimedia data objects that need to be assigned to a storage system consisting of N disks d1,d2,...,dN. We are also given sets U1,U2,...,UM such that Ui is the set of clients requesting the ith data object. Each disk dj is characterized by two parameters, namely, its storage capacity Cj which indicates the maximum number of data objects that may be assigned to it, and a load capacity Lj which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects on disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system. We study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio. Our first main result is a tight upper and lower bound on the number of items that can always be packed for any input instance to homogeneous as well as uniform ratio storage systems. We show that an algorithm given in [11] for data placement, achieves this bound. Our second main result is a polynomial time approximation scheme for the data placement problem in homogeneous and uniform ratio storage systems, answering an open question of [11]. Finally, we also study the problem from an empirical perspective.Publication Asymmetric k-Center is log* n-Hard to Approximate(2004-06-03) Guha, Sudipto; Chuzhoy, Julia; Khanna, Sanjeev; Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Naor, JosephIn the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point to its center is as small as possible. We show that the Asymmetric k-Center problem is hard to approximate up to a factor of log* n - O(1) unless NP is a subset of or equal to DTIME(nlog log n). Since an O(log* n)-approximation algorithm is known for this problem, this resolves the asymptotic approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) k-Center problem with costs.Publication Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing(2010-12-01) Briest, Patrick; Chalermsook, Parinya; Khanna, Sanjeev; Laekhanukit, Bundit; Nanongkai, DanuponWe consider the Stackelberg shortest-path pricing problem, which is defined as follows. Given a graph G with fixed-cost and pricable edges and two distinct vertices s and t, we may assign prices to the pricable edges. Based on the predefined fixed costs and our prices, a customer purchases a cheapest s-t-path in G and we receive payment equal to the sum of prices of pricable edges belonging to the path. Our goal is to find prices maximizing the payment received from the customer. While Stackelberg shortest-path pricing was known to be APX-hard before, we provide the first explicit approximation threshold and prove hardness of approximation within 2−o(1). We also argue that the nicely structured type of instance resulting from our reduction captures most of the challenges we face in dealing with the problem in general and, in particular, we show that the gap between the revenue of an optimal pricing and the only known general upper bound can still be logarithmically large.