×

zbMATH — the first resource for mathematics

Khanna, Sanjeev

Compute Distance To:
Author ID: khanna.sanjeev Recent zbMATH articles by "Khanna, Sanjeev"
Published as: Khanna, S.; Khanna, Sanjeev
Documents Indexed: 134 Publications since 1995, including 3 Books
all top 5

Co-Authors

2 single-authored
23 Chekuri, Chandra S.
13 Chuzhoy, Julia
11 Goel, Ashish
11 Naor, Joseph Seffi
9 Assadi, Sepehr
9 Kapralov, Michael
9 Shepherd, F. Bruce
8 Kannan, Sampath K.
8 Sudan, Madhu
7 Angelov, Stanislav
7 Chakrabarty, Deeparnab
6 Guruswami, Venkatesan
6 Li, Yang
6 Motwani, Rajeev
4 Bhalgat, Anand
4 Chakraborty, Tanmoy
4 Kunal, Keshav
4 Visontai, Mirkó
3 Huang, Zhiyi
3 Raghvendra, Sharath
3 Rajaraman, Rajmohan
3 Zhu, An
2 Aggarwal, Alok
2 Asathulla, Mudabir Kabir
2 Brautbar, Michael
2 Buneman, Peter
2 Chrobak, Marek
2 Coppersmith, Don
2 Dodis, Yevgeniy
2 Draief, Moez
2 Feige, Uriel
2 Golubchik, Leana
2 Guha, Sudipto
2 Hajiaghayi, Mohammad Taghi
2 Halperin, Eran
2 Isler, Volkan
2 Khuller, Samir
2 Kortsarz, Guy
2 Korula, Nitish
2 Lahn, Nathaniel Adam
2 Li, Fei
2 Liberatore, Vincenzo
2 Pierce, Benjamin C.
2 Schieber, Baruch
2 Shepherd, Bruce
2 Talwar, Kunal
2 Tan, Wang-Chiew
2 Tannen, Val
2 Thurimella, Ramakrishna
2 Williamson, David P.
2 Wilson, Randall H.
2 Yannakakis, Mihalis
2 Zhou, Shiyu
2 Zosin, Leonid
1 Adler, Micah
1 Agarwal, Arpit
1 Albers, Susanne
1 Alur, Rajeev
1 Andrews, Matthew T.
1 Arora, Sanjeev
1 Assadi, Sepelir
1 Bansal, Nikhil
1 Batu, Tuğkan
1 Björklund, Andreas
1 Chalermsook, Parinya
1 Charikar, Moses S.
1 Chen, Yu
1 Chen, Yu
1 Chen, Yu
1 Creignou, Nadia
1 Fuchs, W. Kent
1 Goyal, Sanjeev
1 Greenwald, Michael B.
1 Harb, Boulos
1 Hemenway, Brett
1 Hsu, Justin
1 Husfeldt, Thore
1 Jabbari, Shahin
1 Jansen, Klaus
1 Jothimurugan, Kishor
1 Kann, Viggo
1 Kearns, Michael Justin
1 Kim, Junhyong
1 Krauthgamer, Robert
1 Kumar, Amit
1 Lagergren, Jens
1 Larkin, Daniel H.
1 Lee, Insup
1 Li, Shi
1 Linial, Nathan
1 Lucier, Brendan
1 McGregor, Andrew
1 Morgenstern, Jamie
1 Muthukrishnan, S. N.
1 Muthukrishnan, Siddharth
1 Null, Brad
1 Panconesi, Alessandro
1 Paterson, Mike S.
1 Raz, Dan
1 Rolim, José D. P.
...and 18 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

99 Publications have been cited 966 times in 779 Documents Cited by Year
Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058
Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu
107
2001
On syntactic versus computational views of approximability. Zbl 0915.68068
Khanna, Sanjeev; Motwani, Rajeev; Sudan, Madhu; Vazirani, Umesh
60
1998
A polynomial time approximation scheme for the multiple knapsack problem. Zbl 1095.68035
Chekuri, Chandra; Khanna, Sanjeev
37
2006
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
30
2003
Design networks with bounded pairwise distance. Zbl 1345.90032
Dodis, Yevgeniy; Khanna, Sanjeev
24
1999
On multidimensional packing problems. Zbl 1101.68606
Chekuri, Chandra; Khanna, Sanjeev
22
2004
A PTAS for the multiple knapsack problem. Zbl 0952.90020
Chekuri, Chandra; Khanna, Sanjeev
22
2000
An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Zbl 1213.68700
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
20
2006
Improved approximation results for stochastic knapsack problems. Zbl 1373.68450
Bhalgat, Anand; Goel, Ashish; Khanna, Sanjeev
19
2011
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
18
2000
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1292.68090
Chuzhoy, Julia; Khanna, Sanjeev
17
2009
Algorithms for minimizing weighted flow time. Zbl 1323.90019
Chekuri, Chandra; Khanna, Sanjeev; Zhu, An
17
2001
The angular-metric traveling salesman problem. Zbl 0941.68056
Aggarwal, Alok; Coppersmith, Don; Khanna, Sanjeev; Motwani, Rajeev; Schieber, Baruch
16
2000
On approximating rectangle tiling and packing. Zbl 0938.68928
Khanna, Sanjeev; Muthukrishnan, S.; Paterson, Mike
16
1998
On allocating goods to maximize fairness. Zbl 1292.91102
Chakrabarty, Deeparnab; Chuzhoy, Julia; Khanna, Sanjeev
15
2009
Edge-disjoint paths in planar graphs with constant congestion. Zbl 1185.68848
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
15
2009
Randomized pursuit-evasion with local visibility. Zbl 1119.91021
Isler, Volkan; Kannan, Sampath; Khanna, Sanjeev
15
2006
Multicommodity flow, well-linked terminals, and routing problems. Zbl 1192.90017
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
15
2005
On multi-dimensional packing problems. Zbl 0938.68067
Chekuri, Chandra; Khanna, Sanjeev
15
1999
Page replacement for general caching problems. Zbl 0934.68104
Albers, Susanne; Arora, Sanjeev; Khanna, Sanjeev
15
1999
On the hardness of approximating Max \(k\)-Cut and its dual. Zbl 0924.68013
Kann, Viggo; Khanna, Sanjeev; Lagergren, Jens; Panconesi, Alessandro
15
1997
Network design for vertex connectivity. Zbl 1231.68177
Chakraborty, Tanmoy; Chuzfioy, Julia; Khanna, Sanjeev
14
2008
Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation. Zbl 1192.68096
Chekuri, Chandra; Goel, Ashish; Khanna, Sanjeev; Kumar, Amit
14
2004
Approximation algorithms for data placement on parallel disks. Zbl 0961.68010
Golubchik, L.; Khanna, S.; Khuller, S.; Thurimella, R.; Zhu, A.
14
2000
On \((1,\varepsilon)\)-restricted assignment makespan minimization. Zbl 1372.68044
Chakrabarty, Deeparnab; Khanna, Sanjeev; Li, Shi
13
2015
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
13
1999
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068
Khanna, Sanjeev; Sudan, Madhu; Williamson, David P.
13
1999
Towards and syntactic characterization of PTAS. Zbl 0922.68058
Khanna, Sanjeev; Motwani, Rajeev
13
1996
Edge disjoint paths revisited. Zbl 1092.68620
Chekuri, Chandra; Khanna, Sanjeev
12
2003
Improved hardness results for profit maximization pricing problems with unlimited supply. Zbl 1358.91073
Chalermsook, Parinya; Chuzhoy, Julia; Kannan, Sampath; Khanna, Sanjeev
11
2012
Edge-disjoint paths in planar graphs with constant congestion. Zbl 1301.68268
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
11
2006
A linear programming formulation and approximation algorithms for the metric labeling problem. Zbl 1077.68036
Chekuri, C.; Khanna, S.; Naor, J.; Zosin, L.
11
2005
Approximation schemes for preemptive weighted flow time. Zbl 1192.68877
Chekuri, Chandra; Khanna, Sanjeev
11
2002
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Zbl 1240.68113
Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa
10
2010
On the hardness of 4-coloring a 3-colorable graph. Zbl 1087.68071
Guruswami, Venkatesan; Khanna, Sanjeev
10
2004
A PTAS for minimizing weighted completion time on uniformly related machines (extended abstract). Zbl 0986.68503
Chekuri, Chandra; Khanna, Sanjeev
10
2001
Social welfare in one-sided matching markets without money. Zbl 1343.91023
Bhalgat, Anand; Chakrabarty, Deeparnab; Khanna, Sanjeev
8
2011
Polynomial flow-cut gaps and hardness of directed cut problems. Zbl 1325.68096
Chuzhoy, Julia; Khanna, Sanjeev
8
2009
Approximating longest directed paths and cycles. Zbl 1098.68094
Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev
8
2004
Time-constrained scheduling of weighted packets on trees and meshes. Zbl 1053.68013
Adler, Micah; Khanna, Sanjeev; Rajaraman, Rajmohan; Rosén, Adi
8
2003
Why and where: A characterization of data provenance. Zbl 1047.68566
Buneman, Peter; Khanna, Sanjeev; Tan, Wang-Chiew
8
2001
Asymmetric \(k\)-center is \(\log^\ast n\)-hard to approximate. Zbl 1323.68297
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Krauthgamer, Robert; Naor, Joseph
7
2005
Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate. Zbl 1192.68314
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Naor, Joseph
7
2004
Strategic network formation with attack and immunization. Zbl 1404.91055
Goyal, Sanjeev; Jabbari, Shahin; Kearns, Michael; Khanna, Sanjeev; Morgenstern, Jamie
6
2016
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1253.68167
Chuzhoy, Julia; Khanna, Sanjeev
6
2012
Hardness of routing with congestion in directed graphs. Zbl 1232.68062
Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal
6
2007
Hardness of cut problems in directed graphs. Zbl 1301.68155
Chuzhoy, Julia; Khanna, Sanjeev
6
2006
Randomized pursuit-evasion with limited visibility. Zbl 1318.91040
Isler, Volkan; Kannan, Sampath; Khanna, Sanjeev
6
2004
The all-or-nothing multicommodity flow problem. Zbl 1192.68878
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
6
2004
Control message aggregation in group communication protocols. Zbl 1056.68506
Khanna, Sanjeev; Naor, Joseph (Seffi); Raz, Dan
6
2002
A deterministic algorithm for the cost-distance problem. Zbl 1015.90009
Chekuri, Chandra; Khanna, Sanjeev; Naor, Joseph
6
2001
Maximum matchings in dynamic graph streams and the simultaneous communication model. Zbl 1409.68337
Assadi, Sepelir; Khanna, Sanjeev; Li, Yang; Yaroslavtsev, Grigory
5
2016
Approximation algorithms for the metric labeling problem via a new linear programming formulation. Zbl 0989.90104
Chekuri, Chandra; Khanna, Sanjeev; Naor, Joseph; Zosin, Leonid
5
2001
Efficient array partitioning. Zbl 1401.68354
Khanna, Sanjeev; Muthukrishnan, S.; Skiena, Steven
5
1997
On estimating maximum matching size in graph streams. Zbl 1409.68336
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang
4
2017
The all-or-nothing multicommodity flow problem. Zbl 1290.68054
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
4
2013
Distributed private heavy hitters. Zbl 1272.68125
Hsu, Justin; Khanna, Sanjeev; Roth, Aaron
4
2012
Approximability of capacitated network design. Zbl 1339.90321
Chakrabarty, Deeparnab; Chekuri, Chandra; Khanna, Sanjeev; Korula, Nitish
4
2011
Directed network design with orientation constraints. Zbl 1086.68057
Khanna, Sanjeev; Naor, Joseph; Shepherd, F. Bruce
4
2005
Reconstructing strings from random traces. Zbl 1318.68206
Batu, Tuǧkan; Kannan, Sampath; Khanna, Sanjeev; McGregor, Andrew
4
2004
On certificates and lookahead in dynamic graph problems. Zbl 0899.68050
Khanna, S.; Motwani, R.; Wilson, R. H.
4
1998
Perfect matchings in \(O(n\log n)\) time in regular bipartite graphs. Zbl 1272.68154
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
3
2013
Optimal lower bounds for universal and differentially private Steiner trees and TSPs. Zbl 1343.68307
Bhalgat, Anand; Chakrabarty, Deeparnab; Khanna, Sanjeev
3
2011
Dynamic and non-uniform pricing strategies for revenue maximization. Zbl 1292.91069
Chakraborty, Tanmoy; Huang, Zhiyi; Khanna, Sanjeev
3
2009
Nash dynamics in constant player and bounded jump congestion games. Zbl 1262.91014
Chakraborty, Tanmoy; Khanna, Sanjeev
3
2009
A note on multiflows and treewidth. Zbl 1176.90600
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
3
2009
The network as a storage device: dynamic routing with bounded buffers. Zbl 1194.68070
Angelov, Stanislav; Khanna, Sanjeev; Kunal, Keshav
3
2009
Algorithms for 2-route cut problems. Zbl 1153.68566
Chekuri, Chandra; Khanna, Sanjeev
3
2008
On the complexity of graph self-assembly in accretive systems. Zbl 1132.68387
Angelov, Stanislav; Khanna, Sanjeev; Visontai, Mirkó
3
2008
Polynomial flow-cut gaps and hardness of directed cut problems. Zbl 1232.68063
Chuzhoy, Julia; Khanna, Sanjeev
3
2007
Approximating the average response time in broadcast scheduling. Zbl 1297.68038
Bansal, Nikhil; Charikar, Moses; Khanna, Sanjeev; Naor, Joseph (Seffi)
3
2005
The 2-catalog segmentation problem. Zbl 0937.68157
Dodis, Yevgeniy; Guruswami, Venkatesan; Khanna, Sanjeev
3
1999
A linear time algorithm for sequential diagnosis in hypercubes. Zbl 0826.68054
Khanna, Sanjeev; Fuchs, W. Kent
3
1995
Sensitivity and computational complexity in financial networks. Zbl 1396.91823
Hemenway, Brett; Khanna, Sanjeev
2
2016
Tight bounds for single-pass streaming complexity of the set cover problem. Zbl 1373.68250
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang
2
2016
Streaming lower bounds for approximating max-cut. Zbl 1371.68213
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
2
2015
Fast convergence in the double oral auction. Zbl 1406.91156
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang; Vohra, Rakesh
2
2015
Approximating matching size from random streams. Zbl 1423.68344
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
2
2014
A utility equivalence theorem for concave functions. Zbl 1410.91224
Bhalgat, Anand; Khanna, Sanjeev
2
2014
Dynamic and nonuniform pricing strategies for revenue maximization. Zbl 1285.91046
Chakraborty, Tanmoy; Huang, Zhiyi; Khanna, Sanjeev
2
2013
Algorithms for the generalized sorting problem. Zbl 1292.68042
Huang, Zhiyi; Kannan, Sampath; Khanna, Sanjeev
2
2011
Perfect matchings via uniform sampling in regular bipartite graphs. Zbl 1300.05252
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
2
2010
Perfect matchings in \(O(n \log n)\) time in regular bipartite graphs. Zbl 1293.05291
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
2
2010
Approximation algorithms for data placement on parallel disks. Zbl 1298.68294
Golubchik, Leana; Khanna, Sanjeev; Khuller, Samir; Thurimella, Ramakrishna; Zhu, An
2
2009
On the complexity of graph self-assembly in accretive systems. Zbl 1146.68056
Angelov, Stanislav; Khanna, Sanjeev; Visontai, Mirkó
2
2008
Selection with monotone comparison costs. Zbl 1094.68551
Kannan, Sampath; Khanna, Sanjeev
2
2003
Directed network design with orientation constraints. Zbl 0972.90006
Khanna, Sanjeev; Naor, Joseph; Shepherd, F. Bruce
2
2000
The angular-metric traveling salesman problem. Zbl 1321.68293
Aggarwal, Alok; Coppersmith, Don; Khanna, Sanjeev; Motwani, Rajeev; Schieber, Baruch
2
1997
On certificates and lookahead in dynamic graph problems. Zbl 0848.68075
Khanna, Sanjeev; Motwani, Rajeev; Wilson, Randall H.
2
1996
Sublinear algorithms for \((\Delta + 1)\) vertex coloring. Zbl 1431.68174
Assadi, Sepehr; Chen, Yu; Khanna, Sanjeev
1
2019
Tight bounds on the round complexity of the distributed maximum coverage problem. Zbl 1403.68325
Assadi, Sepehr; Khanna, Sanjeev
1
2018
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya
1
2017
Approximability of capacitated network design. Zbl 1327.90023
Chakrabarty, Deeparnab; Chekuri, Chandra; Khanna, Sanjeev; Korula, Nitish
1
2015
On the communication and streaming complexity of maximum bipartite matching. Zbl 1421.68130
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
1
2012
The ratio index for budgeted learning, with applications. Zbl 1421.68223
Goel, Ashish; Khanna, Sanjeev; Null, Brad
1
2009
Agreeing to agree: Conflict resolution for optimistically replicated data. Zbl 1155.68330
Greenwald, Michael B.; Khanna, Sanjeev; Kunal, Keshav; Pierce, Benjamin C.; Schmitt, Alan
1
2007
A formal investigation of diff3. Zbl 1135.68375
Khanna, Sanjeev; Kunal, Keshav; Pierce, Benjamin C.
1
2007
On indexed data broadcast. Zbl 1028.68047
Khanna, Sanjeev; Zhou, Shiyu
1
1998
Sublinear algorithms for \((\Delta + 1)\) vertex coloring. Zbl 1431.68174
Assadi, Sepehr; Chen, Yu; Khanna, Sanjeev
1
2019
Tight bounds on the round complexity of the distributed maximum coverage problem. Zbl 1403.68325
Assadi, Sepehr; Khanna, Sanjeev
1
2018
On estimating maximum matching size in graph streams. Zbl 1409.68336
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang
4
2017
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya
1
2017
Strategic network formation with attack and immunization. Zbl 1404.91055
Goyal, Sanjeev; Jabbari, Shahin; Kearns, Michael; Khanna, Sanjeev; Morgenstern, Jamie
6
2016
Maximum matchings in dynamic graph streams and the simultaneous communication model. Zbl 1409.68337
Assadi, Sepelir; Khanna, Sanjeev; Li, Yang; Yaroslavtsev, Grigory
5
2016
Sensitivity and computational complexity in financial networks. Zbl 1396.91823
Hemenway, Brett; Khanna, Sanjeev
2
2016
Tight bounds for single-pass streaming complexity of the set cover problem. Zbl 1373.68250
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang
2
2016
On \((1,\varepsilon)\)-restricted assignment makespan minimization. Zbl 1372.68044
Chakrabarty, Deeparnab; Khanna, Sanjeev; Li, Shi
13
2015
Streaming lower bounds for approximating max-cut. Zbl 1371.68213
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
2
2015
Fast convergence in the double oral auction. Zbl 1406.91156
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang; Vohra, Rakesh
2
2015
Approximability of capacitated network design. Zbl 1327.90023
Chakrabarty, Deeparnab; Chekuri, Chandra; Khanna, Sanjeev; Korula, Nitish
1
2015
Approximating matching size from random streams. Zbl 1423.68344
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
2
2014
A utility equivalence theorem for concave functions. Zbl 1410.91224
Bhalgat, Anand; Khanna, Sanjeev
2
2014
The all-or-nothing multicommodity flow problem. Zbl 1290.68054
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
4
2013
Perfect matchings in \(O(n\log n)\) time in regular bipartite graphs. Zbl 1272.68154
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
3
2013
Dynamic and nonuniform pricing strategies for revenue maximization. Zbl 1285.91046
Chakraborty, Tanmoy; Huang, Zhiyi; Khanna, Sanjeev
2
2013
Improved hardness results for profit maximization pricing problems with unlimited supply. Zbl 1358.91073
Chalermsook, Parinya; Chuzhoy, Julia; Kannan, Sampath; Khanna, Sanjeev
11
2012
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1253.68167
Chuzhoy, Julia; Khanna, Sanjeev
6
2012
Distributed private heavy hitters. Zbl 1272.68125
Hsu, Justin; Khanna, Sanjeev; Roth, Aaron
4
2012
On the communication and streaming complexity of maximum bipartite matching. Zbl 1421.68130
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
1
2012
Improved approximation results for stochastic knapsack problems. Zbl 1373.68450
Bhalgat, Anand; Goel, Ashish; Khanna, Sanjeev
19
2011
Social welfare in one-sided matching markets without money. Zbl 1343.91023
Bhalgat, Anand; Chakrabarty, Deeparnab; Khanna, Sanjeev
8
2011
Approximability of capacitated network design. Zbl 1339.90321
Chakrabarty, Deeparnab; Chekuri, Chandra; Khanna, Sanjeev; Korula, Nitish
4
2011
Optimal lower bounds for universal and differentially private Steiner trees and TSPs. Zbl 1343.68307
Bhalgat, Anand; Chakrabarty, Deeparnab; Khanna, Sanjeev
3
2011
Algorithms for the generalized sorting problem. Zbl 1292.68042
Huang, Zhiyi; Kannan, Sampath; Khanna, Sanjeev
2
2011
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Zbl 1240.68113
Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa
10
2010
Perfect matchings via uniform sampling in regular bipartite graphs. Zbl 1300.05252
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
2
2010
Perfect matchings in \(O(n \log n)\) time in regular bipartite graphs. Zbl 1293.05291
Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev
2
2010
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1292.68090
Chuzhoy, Julia; Khanna, Sanjeev
17
2009
On allocating goods to maximize fairness. Zbl 1292.91102
Chakrabarty, Deeparnab; Chuzhoy, Julia; Khanna, Sanjeev
15
2009
Edge-disjoint paths in planar graphs with constant congestion. Zbl 1185.68848
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
15
2009
Polynomial flow-cut gaps and hardness of directed cut problems. Zbl 1325.68096
Chuzhoy, Julia; Khanna, Sanjeev
8
2009
Dynamic and non-uniform pricing strategies for revenue maximization. Zbl 1292.91069
Chakraborty, Tanmoy; Huang, Zhiyi; Khanna, Sanjeev
3
2009
Nash dynamics in constant player and bounded jump congestion games. Zbl 1262.91014
Chakraborty, Tanmoy; Khanna, Sanjeev
3
2009
A note on multiflows and treewidth. Zbl 1176.90600
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
3
2009
The network as a storage device: dynamic routing with bounded buffers. Zbl 1194.68070
Angelov, Stanislav; Khanna, Sanjeev; Kunal, Keshav
3
2009
Approximation algorithms for data placement on parallel disks. Zbl 1298.68294
Golubchik, Leana; Khanna, Sanjeev; Khuller, Samir; Thurimella, Ramakrishna; Zhu, An
2
2009
The ratio index for budgeted learning, with applications. Zbl 1421.68223
Goel, Ashish; Khanna, Sanjeev; Null, Brad
1
2009
Network design for vertex connectivity. Zbl 1231.68177
Chakraborty, Tanmoy; Chuzfioy, Julia; Khanna, Sanjeev
14
2008
Algorithms for 2-route cut problems. Zbl 1153.68566
Chekuri, Chandra; Khanna, Sanjeev
3
2008
On the complexity of graph self-assembly in accretive systems. Zbl 1132.68387
Angelov, Stanislav; Khanna, Sanjeev; Visontai, Mirkó
3
2008
On the complexity of graph self-assembly in accretive systems. Zbl 1146.68056
Angelov, Stanislav; Khanna, Sanjeev; Visontai, Mirkó
2
2008
Hardness of routing with congestion in directed graphs. Zbl 1232.68062
Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal
6
2007
Polynomial flow-cut gaps and hardness of directed cut problems. Zbl 1232.68063
Chuzhoy, Julia; Khanna, Sanjeev
3
2007
Agreeing to agree: Conflict resolution for optimistically replicated data. Zbl 1155.68330
Greenwald, Michael B.; Khanna, Sanjeev; Kunal, Keshav; Pierce, Benjamin C.; Schmitt, Alan
1
2007
A formal investigation of diff3. Zbl 1135.68375
Khanna, Sanjeev; Kunal, Keshav; Pierce, Benjamin C.
1
2007
A polynomial time approximation scheme for the multiple knapsack problem. Zbl 1095.68035
Chekuri, Chandra; Khanna, Sanjeev
37
2006
An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Zbl 1213.68700
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
20
2006
Randomized pursuit-evasion with local visibility. Zbl 1119.91021
Isler, Volkan; Kannan, Sampath; Khanna, Sanjeev
15
2006
Edge-disjoint paths in planar graphs with constant congestion. Zbl 1301.68268
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
11
2006
Hardness of cut problems in directed graphs. Zbl 1301.68155
Chuzhoy, Julia; Khanna, Sanjeev
6
2006
Multicommodity flow, well-linked terminals, and routing problems. Zbl 1192.90017
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
15
2005
A linear programming formulation and approximation algorithms for the metric labeling problem. Zbl 1077.68036
Chekuri, C.; Khanna, S.; Naor, J.; Zosin, L.
11
2005
Asymmetric \(k\)-center is \(\log^\ast n\)-hard to approximate. Zbl 1323.68297
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Krauthgamer, Robert; Naor, Joseph
7
2005
Directed network design with orientation constraints. Zbl 1086.68057
Khanna, Sanjeev; Naor, Joseph; Shepherd, F. Bruce
4
2005
Approximating the average response time in broadcast scheduling. Zbl 1297.68038
Bansal, Nikhil; Charikar, Moses; Khanna, Sanjeev; Naor, Joseph (Seffi)
3
2005
On multidimensional packing problems. Zbl 1101.68606
Chekuri, Chandra; Khanna, Sanjeev
22
2004
Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation. Zbl 1192.68096
Chekuri, Chandra; Goel, Ashish; Khanna, Sanjeev; Kumar, Amit
14
2004
On the hardness of 4-coloring a 3-colorable graph. Zbl 1087.68071
Guruswami, Venkatesan; Khanna, Sanjeev
10
2004
Approximating longest directed paths and cycles. Zbl 1098.68094
Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev
8
2004
Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate. Zbl 1192.68314
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Naor, Joseph
7
2004
Randomized pursuit-evasion with limited visibility. Zbl 1318.91040
Isler, Volkan; Kannan, Sampath; Khanna, Sanjeev
6
2004
The all-or-nothing multicommodity flow problem. Zbl 1192.68878
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
6
2004
Reconstructing strings from random traces. Zbl 1318.68206
Batu, Tuǧkan; Kannan, Sampath; Khanna, Sanjeev; McGregor, Andrew
4
2004
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
30
2003
Edge disjoint paths revisited. Zbl 1092.68620
Chekuri, Chandra; Khanna, Sanjeev
12
2003
Time-constrained scheduling of weighted packets on trees and meshes. Zbl 1053.68013
Adler, Micah; Khanna, Sanjeev; Rajaraman, Rajmohan; Rosén, Adi
8
2003
Selection with monotone comparison costs. Zbl 1094.68551
Kannan, Sampath; Khanna, Sanjeev
2
2003
Approximation schemes for preemptive weighted flow time. Zbl 1192.68877
Chekuri, Chandra; Khanna, Sanjeev
11
2002
Control message aggregation in group communication protocols. Zbl 1056.68506
Khanna, Sanjeev; Naor, Joseph (Seffi); Raz, Dan
6
2002
Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058
Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu
107
2001
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
Algorithms for minimizing weighted flow time. Zbl 1323.90019
Chekuri, Chandra; Khanna, Sanjeev; Zhu, An
17
2001
A PTAS for minimizing weighted completion time on uniformly related machines (extended abstract). Zbl 0986.68503
Chekuri, Chandra; Khanna, Sanjeev
10
2001
Why and where: A characterization of data provenance. Zbl 1047.68566
Buneman, Peter; Khanna, Sanjeev; Tan, Wang-Chiew
8
2001
A deterministic algorithm for the cost-distance problem. Zbl 1015.90009
Chekuri, Chandra; Khanna, Sanjeev; Naor, Joseph
6
2001
Approximation algorithms for the metric labeling problem via a new linear programming formulation. Zbl 0989.90104
Chekuri, Chandra; Khanna, Sanjeev; Naor, Joseph; Zosin, Leonid
5
2001
A PTAS for the multiple knapsack problem. Zbl 0952.90020
Chekuri, Chandra; Khanna, Sanjeev
22
2000
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
18
2000
The angular-metric traveling salesman problem. Zbl 0941.68056
Aggarwal, Alok; Coppersmith, Don; Khanna, Sanjeev; Motwani, Rajeev; Schieber, Baruch
16
2000
Approximation algorithms for data placement on parallel disks. Zbl 0961.68010
Golubchik, L.; Khanna, S.; Khuller, S.; Thurimella, R.; Zhu, A.
14
2000
Directed network design with orientation constraints. Zbl 0972.90006
Khanna, Sanjeev; Naor, Joseph; Shepherd, F. Bruce
2
2000
Design networks with bounded pairwise distance. Zbl 1345.90032
Dodis, Yevgeniy; Khanna, Sanjeev
24
1999
On multi-dimensional packing problems. Zbl 0938.68067
Chekuri, Chandra; Khanna, Sanjeev
15
1999
Page replacement for general caching problems. Zbl 0934.68104
Albers, Susanne; Arora, Sanjeev; Khanna, Sanjeev
15
1999
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
13
1999
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068
Khanna, Sanjeev; Sudan, Madhu; Williamson, David P.
13
1999
The 2-catalog segmentation problem. Zbl 0937.68157
Dodis, Yevgeniy; Guruswami, Venkatesan; Khanna, Sanjeev
3
1999
On syntactic versus computational views of approximability. Zbl 0915.68068
Khanna, Sanjeev; Motwani, Rajeev; Sudan, Madhu; Vazirani, Umesh
60
1998
On approximating rectangle tiling and packing. Zbl 0938.68928
Khanna, Sanjeev; Muthukrishnan, S.; Paterson, Mike
16
1998
On certificates and lookahead in dynamic graph problems. Zbl 0899.68050
Khanna, S.; Motwani, R.; Wilson, R. H.
4
1998
On indexed data broadcast. Zbl 1028.68047
Khanna, Sanjeev; Zhou, Shiyu
1
1998
On the hardness of approximating Max \(k\)-Cut and its dual. Zbl 0924.68013
Kann, Viggo; Khanna, Sanjeev; Lagergren, Jens; Panconesi, Alessandro
15
1997
Efficient array partitioning. Zbl 1401.68354
Khanna, Sanjeev; Muthukrishnan, S.; Skiena, Steven
5
1997
The angular-metric traveling salesman problem. Zbl 1321.68293
Aggarwal, Alok; Coppersmith, Don; Khanna, Sanjeev; Motwani, Rajeev; Schieber, Baruch
2
1997
Towards and syntactic characterization of PTAS. Zbl 0922.68058
Khanna, Sanjeev; Motwani, Rajeev
13
1996
On certificates and lookahead in dynamic graph problems. Zbl 0848.68075
Khanna, Sanjeev; Motwani, Rajeev; Wilson, Randall H.
2
1996
A linear time algorithm for sequential diagnosis in hypercubes. Zbl 0826.68054
Khanna, Sanjeev; Fuchs, W. Kent
3
1995
all top 5

Cited by 1,429 Authors

18 Nutov, Zeev
14 Krokhin, Andrei A.
12 Creignou, Nadia
12 Shachnai, Hadas
11 Chekuri, Chandra S.
11 Jansen, Klaus
11 Kortsarz, Guy
11 Živný, Stanislav
10 Bazgan, Cristina
10 Chen, Hubie
10 Levin, Asaf
9 Epstein, Leah
9 Jeavons, Peter G.
9 Khanna, Sanjeev
9 Paschos, Vangelis Th.
8 Hajiaghayi, Mohammad Taghi
8 Jonsson, Peter A.
8 Nagarajan, Viswanath
8 Tamir, Tami
7 Bentz, Cédric
7 Bulatov, Andrei A.
7 Wiese, Andreas
6 Bansal, Nikhil
6 Cai, Jin-Yi
6 Cohen, David A.
6 Guruswami, Venkatesan
6 Halldórsson, Magnús Mar
6 Khandekar, Rohit
6 Lu, Pinyan
6 Rawitz, Dror
6 Salavatipour, Mohammad R.
6 Thapper, Johan
6 Vollmer, Heribert
5 Bodirsky, Manuel
5 Chakrabarty, Deeparnab
5 Cooper, Martin C.
5 Dalmau, Víctor
5 Demange, Marc
5 Fischer, Anja
5 Goldberg, Leslie Ann
5 Hermann, Miki
5 Martin, Barnaby D.
5 Patt-Shamir, Boaz
5 Ravi, Ramamoorthi
5 Salzer, Gernot
5 Solis-Oba, Roberto
5 Trevisan, Luca
5 Zhang, Yong
4 Ausiello, Giorgio
4 Borodin, Allan B.
4 Chin, Francis Y. L.
4 Chrobak, Marek
4 Chuzhoy, Julia
4 Ene, Alina
4 Escoffier, Bruno
4 Friggstad, Zachary
4 Garg, Naveen Kumar
4 Im, Sungjin
4 Kawarabayashi, Ken-ichi
4 Kobayashi, Yusuke
4 Kolman, Petr
4 Krishnaswamy, Ravishankar
4 Kumar, Amit
4 Laekhanukit, Bundit
4 Maack, Marten
4 Marathe, Madhav V.
4 Marx, Dániel
4 Moseley, Benjamin
4 Page, Daniel R.
4 Schieber, Baruch
4 Singh, Mohit
4 Thilikos, Dimitrios M.
4 Ting, Hing-Fung
4 Xavier, Eduardo Candido
4 Xu, Dachuan
3 Anshelevich, Elliot
3 Bauland, Michael
3 Behrisch, Mike
3 Chen, Danny Ziyi
3 Chen, Jian-er
3 Cheriyan, Joseph
3 Chlamtac, Eden
3 Choudhury, Anamitra Roy
3 Crescenzi, Pierluigi
3 Dyer, Martin E.
3 Erlebach, Thomas
3 Fischer, Frank
3 Georgiou, Konstantinos
3 Grandoni, Fabrizio
3 Gudmundsson, Joachim
3 Guo, Heng
3 Gupta, Anupam
3 Hunt, Harry Bowen III
3 Imreh, Csanád
3 Jerrum, Mark R.
3 Jiang, Minghui
3 Kellerer, Johann
3 Khuller, Samir
3 Kleiman, Elena
3 Klimm, Max
...and 1,329 more Authors
all top 5

Cited in 109 Serials

104 Theoretical Computer Science
80 Algorithmica
39 Discrete Applied Mathematics
38 SIAM Journal on Computing
31 Journal of Combinatorial Optimization
29 Theory of Computing Systems
27 Information Processing Letters
27 Journal of Computer and System Sciences
23 Mathematical Programming. Series A. Series B
20 European Journal of Operational Research
14 Operations Research Letters
13 Journal of Scheduling
11 Information and Computation
11 Discrete Optimization
9 Games and Economic Behavior
9 Journal of Discrete Algorithms
8 SIAM Journal on Discrete Mathematics
7 Annals of Operations Research
6 Artificial Intelligence
6 Networks
6 Journal of Parallel and Distributed Computing
6 Computational Geometry
6 Constraints
5 Mathematics of Operations Research
5 European Journal of Combinatorics
5 Annals of Mathematics and Artificial Intelligence
5 Optimization Letters
4 Combinatorica
4 Computers & Operations Research
4 Distributed Computing
4 SIAM Journal on Optimization
4 Journal of Machine Learning Research (JMLR)
4 4OR
4 Computer Science Review
3 Algebra Universalis
3 Journal of Graph Theory
3 International Journal of Foundations of Computer Science
3 Computational Complexity
2 Discrete Mathematics
2 Automatica
2 Journal of Combinatorial Theory. Series B
2 Naval Research Logistics
2 Operations Research
2 International Journal of Approximate Reasoning
2 Mathematical and Computer Modelling
2 Real-Time Systems
2 International Journal of Computational Geometry & Applications
2 The Annals of Applied Probability
2 International Journal of Algebra and Computation
2 Journal of Global Optimization
2 International Journal of Computer Vision
2 INFORMS Journal on Computing
2 RAIRO. Theoretical Informatics and Applications
2 RAIRO. Operations Research
2 Natural Computing
2 SIAM Journal on Imaging Sciences
2 Algorithms
2 Journal of the Operations Research Society of China
1 Acta Informatica
1 Communications in Mathematical Physics
1 Israel Journal of Mathematics
1 Journal of the Franklin Institute
1 ACM Transactions on Database Systems
1 Journal of Economic Theory
1 Mathematische Annalen
1 SIAM Journal on Control and Optimization
1 SIAM Journal on Numerical Analysis
1 Mathematical Social Sciences
1 Parallel Computing
1 Optimization
1 Journal of Computer Science and Technology
1 Journal of Automated Reasoning
1 Asia-Pacific Journal of Operational Research
1 Journal of Economic Dynamics & Control
1 Applied Mathematics Letters
1 Journal of Cryptology
1 Neural Networks
1 Machine Learning
1 Random Structures & Algorithms
1 YUJOR. Yugoslav Journal of Operations Research
1 International Journal of Computer Mathematics
1 Stochastic Processes and their Applications
1 Cybernetics and Systems Analysis
1 Combinatorics, Probability and Computing
1 Top
1 Optimization Methods & Software
1 Annals of Combinatorics
1 Wuhan University Journal of Natural Sciences (WUJNS)
1 Data Mining and Knowledge Discovery
1 Annals of Mathematics. Second Series
1 Theory and Practice of Logic Programming
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 ACM Transactions on Computational Logic
1 ACM Journal of Experimental Algorithmics
1 Journal of Applied Logic
1 Journal of Industrial and Management Optimization
1 International Journal of Parallel, Emergent and Distributed Systems
1 Communications in Mathematical Analysis
1 Electronic Journal of Statistics
1 Science China. Information Sciences
...and 9 more Serials

Citations by Year