dblp.uni-trier.de

Sanjeev Khanna

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2007
102EESanjeev Khanna, Keshav Kunal, Benjamin C. Pierce: A Formal Investigation of. FSTTCS 2007: 485-496
101EEJulia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar: Hardness of routing with congestion in directed graphs. STOC 2007: 165-178
100EEJulia Chuzhoy, Sanjeev Khanna: Polynomial flow-cut gaps and hardness of directed cut problems. STOC 2007: 179-188
2006
99EEMichael B. Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, Alan Schmitt: Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data. DISC 2006: 269-283
98EEStanislav Angelov, Sanjeev Khanna, Mirkó Visontai: On the Complexity of Graph Self-assembly in Accretive Systems. DNA 2006: 95-110
97EEStanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim: Efficient Enumeration of Phylogenetically Informative Substrings. RECOMB 2006: 248-264
96EEJulia Chuzhoy, Sanjeev Khanna: Hardness of cut problems in directed graphs. STOC 2006: 527-536
95EEChandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-disjoint paths in Planar graphs with constant congestion. STOC 2006: 757-766
94EEVolkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized Pursuit-Evasion with Local Visibility. SIAM J. Discrete Math. 20(1): 26-41 (2006)
2005
93EEStanislav Angelov, Sanjeev Khanna, Keshav Kunal: The Network as a Storage Device: Dynamic Routing with Bounded Buffers. APPROX-RANDOM 2005: 1-13
92EEMatthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang: Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. FOCS 2005: 226-244
91EENikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor: Approximating the average response time in broadcast scheduling. SODA 2005: 215-221
90EEChandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. STOC 2005: 183-192
89EEVolkan Isler, Sanjeev Khanna, John R. Spletzer, Camillo J. Taylor: Target tracking with distributed sensors: The focus of attention problem. Computer Vision and Image Understanding 100(1-2): 225-247 (2005)
88EEJulia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. J. ACM 52(4): 538-551 (2005)
87EEChandra Chekuri, Sanjeev Khanna: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM J. Comput. 35(3): 713-728 (2005)
2004
86 Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron: Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings Springer 2004
85EEChandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-Disjoint Paths in Planar Graphs. FOCS 2004: 71-80
84EEJulia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90
83EEAndreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Paths and Cycles. ICALP 2004: 222-233
82EECarl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh: DoS Protection for Reliably Authenticated Broadcast. NDSS 2004
81EEMichael Greenwald, Sanjeev Khanna: Power-Conserving Computation of Order-Statistics over Sensor Networks. PODS 2004: 275-285
80EEVolkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized pursuit-evasion with limited visibility. SODA 2004: 1060-1069
79EETugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor: Reconstructing strings from random traces. SODA 2004: 910-918
78EEChandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: The all-or-nothing multicommodity flow problem. STOC 2004: 156-165
77EEJulia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. STOC 2004: 21-27
76EEChandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. STOC 2004: 363-372
75EEStanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira: ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. WABI 2004: 206-217
74EEStanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang: Genome Identification and Classification by Short Oligo Arrays. WABI 2004: 400-411
73EEPeter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving scientific data. ACM Trans. Database Syst. 29: 2-42 (2004)
72EESanjeev Khanna, Aravind Srinivasan: Special issue: 35th Annual ACM Symposium on Theory of Computing. J. Comput. Syst. Sci. 69(3): 305- (2004)
71EEChandra Chekuri, Sanjeev Khanna: On Multidimensional Packing Problems. SIAM J. Comput. 33(4): 837-851 (2004)
70EEVenkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discrete Math. 18(1): 30-40 (2004)
69EEChandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discrete Math. 18(3): 608-625 (2004)
2003
68EESampath Kannan, Sanjeev Khanna: Selection with monotone comparison cost. SODA 2003: 10-17
67EEChandra Chekuri, Sanjeev Khanna: Edge disjoint paths revisited. SODA 2003: 628-637
66EEMicah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén: Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. Algorithmica 36(2): 123-152 (2003)
65EEAndreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Path Electronic Colloquium on Computational Complexity (ECCC) 10(032): (2003)
64EEJulia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Asymmetric k-center is log*n-hard to Approximate Electronic Colloquium on Computational Complexity (ECCC)(038): (2003)
63EEVenkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3): 473-496 (2003)
2002
62EESanjeev Khanna, Joseph Naor, Danny Raz: Control Message Aggregation in Group Communication Protocols. ICALP 2002: 135-146
61EEPeter Buneman, Sanjeev Khanna, Wang Chiew Tan: On Propagation of Deletions and Annotations Through Views. PODS 2002: 150-158
60EEPeter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving scientific data. SIGMOD Conference 2002: 1-12
59EEChandra Chekuri, Sanjeev Khanna: Approximation schemes for preemptive weighted flow time. STOC 2002: 297-305
58EESanjeev Khanna: Guest Editor's Foreword. J. Comput. Syst. Sci. 64(4): 749 (2002)
2001
57EEChandra Chekuri, Sanjeev Khanna: A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. ICALP 2001: 848-861
56EEPeter Buneman, Sanjeev Khanna, Wang Chiew Tan: Why and Where: A Characterization of Data Provenance. ICDT 2001: 316-330
55EEMaria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou: Fair Real-Time Traffic Scheduling over a Wireless LA. IEEE Real-Time Systems Symposium 2001: 279-288
54EESanjeev Khanna, Wang Chiew Tan: On Computing Functions with Uncertainty. PODS 2001
53EEMichael Greenwald, Sanjeev Khanna: Space-Efficient Online Computation of Quantile Summaries. SIGMOD Conference 2001: 58-66
52EEChandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: Approximation algorithms for the metric labeling problem via a new linear programming formulation. SODA 2001: 109-118
51EEChandra Chekuri, Sanjeev Khanna, Joseph Naor: A deterministic algorithm for the cost-distance problem. SODA 2001: 232-233
50EEChandra Chekuri, Sanjeev Khanna, An Zhu: Algorithms for minimizing weighted flow time. STOC 2001: 84-93
49EEChandra Chekuri, Sanjeev Khanna: Approximation Schemes for Preemptive Weighted Flow Time Electronic Colloquium on Computational Complexity (ECCC) 8(065): (2001)
2000
48EEPeter Buneman, Sanjeev Khanna, Wang Chiew Tan: Data Provenance: Some Basic Issues. FSTTCS 2000: 87-93
47EEVenkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. IEEE Conference on Computational Complexity 2000: 188-197
46EEChandra Chekuri, Sanjeev Khanna: A PTAS for the multiple knapsack problem. SODA 2000: 213-222
45EELeana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu: Approximation algorithms for data placement on parallel disks. SODA 2000: 223-232
44EESanjeev Khanna, Francis Zane: Watermarking maps: hiding information in structured data. SODA 2000: 596-605
43EESanjeev Khanna, Joseph Naor, F. Bruce Shepherd: Directed network design with orientation constraints. SODA 2000: 663-671
42EESanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. Combinatorica 20(3): 393-415 (2000)
41EEVenkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-coloring a 3-colorable Graph Electronic Colloquium on Computational Complexity (ECCC) 7(73): (2000)
40 Sanjeev Khanna, Shiyu Zhou: On Indexed Data Broadcast J. Comput. Syst. Sci. 60(3): 575-591 (2000)
39 Sanjeev Khanna, Vincenzo Liberatore: On Broadcast Disk Paging. SIAM J. Comput. 29(5): 1683-1702 (2000)
38EESanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)
1999
37EEFoto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS 1999: 32-44
36EEYevgeniy Dodis, Sanjeev Khanna: Space Time Tradeoffs for Graph Properties. ICALP 1999: 291-300
35 Matthew Andrews, Sanjeev Khanna, Krishnan Kumaran: Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch. INFOCOM 1999: 1144-1151
34EEChandra Chekuri, Sanjeev Khanna: On Multi-Dimensional Packing Problems. SODA 1999: 185-194
33EESusanne Albers, Sanjeev Arora, Sanjeev Khanna: Page Replacement for General Caching Problems. SODA 1999: 31-40
32EEYevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna: The 2-Catalog Segmentation Problem. SODA 1999: 897-898
31EEMicah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén: Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. SPAA 1999: 1-12
30EEVenkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC 1999: 19-28
29EEYevgeniy Dodis, Sanjeev Khanna: Design Networks with Bounded Pairwise Distance. STOC 1999: 750-759
28 Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber: The Angular-Metric Traveling Salesman Problem. SIAM J. Comput. 29(3): 697-711 (1999)
1998
27 Krishnan Kumaran, Sanjeev Khanna: On Wireless Spectrum Estimation and Generalized Graph Coloring. INFOCOM 1998: 1273-1283
26 Sanjeev Khanna, S. Muthukrishnan, Mike Paterson: On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393
25EESanjeev Khanna, Shiyu Zhou: On Indexed Data Broadcast. STOC 1998: 463-472
24EESanjeev Khanna, Vincenzo Liberatore: On Broadcast Disk Paging. STOC 1998: 634-643
23 Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson: On Certificates and Lookahead in Dynamic Graph Problems. Algorithmica 21(4): 377-394 (1998)
22 Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998)
1997
21 Sanjeev Khanna, S. Muthukrishnan, Steven Skiena: Efficient Array Partitioning. ICALP 1997: 616-626
20EESanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint Satisfaction: The Approximability of Minimization Problems. IEEE Conference on Computational Complexity 1997: 282-296
19 Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber: The Angular-Metric Traveling Salesman Problem. SODA 1997: 221-229
18EESanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20
17EEViggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi: On the Hardness of Approximating Max k-Cut and its Dual. Chicago J. Theor. Comput. Sci. 1997: (1997)
16 Sanjeev Khanna, W. Kent Fuchs: A Graph Partitioning Approach to Sequential Diagnosis. IEEE Trans. Computers 46(1): 39-47 (1997)
1996
15 Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi: On the Hardness of Approximating Max k-Cut and Its Dual. ISTCS 1996: 61-67
14 Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson: On Certificates and Lookahead in Dynamic Graph Problems. SODA 1996: 222-231
13EESanjeev Khanna, Rajeev Motwani: Towards a Syntactic Characterization of PTAS. STOC 1996: 329-337
12EESanjeev Khanna, Madhu Sudan: The Optimization Complexity of Constraint Satisfaction Problems Electronic Colloquium on Computational Complexity (ECCC) 3(28): (1996)
11EESanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction Electronic Colloquium on Computational Complexity (ECCC) 3(62): (1996)
10EESanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint satisfaction: The approximability of minimization problems. Electronic Colloquium on Computational Complexity (ECCC) 3(64): (1996)
1995
9EESanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability Electronic Colloquium on Computational Complexity (ECCC) 2(23): (1995)
8 Sanjeev Khanna, W. Kent Fuchs: A Linear Time Algorithm for Sequential Diagnosis in Hypercubes. J. Parallel Distrib. Comput. 26(1): 48-53 (1995)
1994
7 Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability FOCS 1994: 819-830
1993
6 Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260
1992
5 Kurt Maly, Sanjeev Khanna, Ravi Mukkamala, C. Michael Overstreet, Ramesh Yerraballi, Edwin C. Foudriat, B. Madan: Parallel TCP/IP for Multiprocessor Workstations. HPN 1992: 103-118
4 Kurt Maly, Frank Paterra, C. Michael Overstreet, Ravi Mukkamala, Sanjeev Khanna: Concurrent Use of Parallel Communication to Enable Remote Visualization. ICCI 1992: 449-452
3 Kurt Maly, Sanjeev Khanna, C. Michael Overstreet, Ravi Mukkamala, Mohammad Zubair, Y. S. Sekhar: Multiprocessor Architectures for High Speed Networks: A Performance Study. IFIP Congress (1) 1992: 645-651
1991
2 Sanjeev Khanna: Logic Programming for Software Verification and Testing. Comput. J. 34(4): 350-357 (1991)
1990
1 Sanjeev Khanna: Logic Programming for Software Testing. ICCI 1990: 225-234

Coauthor Index

1Maria Adamou [55]
2Micah Adler [31] [66]
3Foto N. Afrati [37]
4Alok Aggarwal [19] [28]
5Susanne Albers [33]
6Matthew Andrews [35] [92]
7Stanislav Angelov [74] [75] [93] [97] [98]
8Sanjeev Arora [33]
9Evripidis Bampis [37]
10Nikhil Bansal [91]
11Tugkan Batu [79]
12Andreas Björklund [65] [83]
13Peter Buneman [48] [56] [60] [61] [73]
14Moses Charikar [91]
15Chandra Chekuri [34] [37] [46] [49] [50] [51] [52] [57] [59] [67] [69] [71] [76] [78] [85] [87] [90] [95]
16Julia Chuzhoy [64] [77] [84] [88] [92] [96] [100] [101]
17Don Coppersmith [19] [28]
18Yevgeniy Dodis [29] [32] [36]
19Edwin C. Foudriat [5]
20W. Kent Fuchs [8] [16]
21Ashish Goel [76]
22Leana Golubchik [45]
23Michael B. Greenwald (Michael Greenwald) [53] [81] [99]
24Sudipto Guha [64] [77] [84] [88]
25Carl A. Gunter [82]
26Venkatesan Guruswami [30] [32] [41] [47] [63] [70] [101]
27Eran Halperin [77] [88]
28Boulos Harb [74] [97]
29Thore Husfeldt [65] [83]
30Volkan Isler [80] [89] [94]
31Klaus Jansen [86]
32Viggo Kann [15] [17]
33Sampath Kannan [68] [74] [79] [80] [94] [97]
34David R. Karger [37]
35Samir Khuller [45]
36Junhyong Kim [74] [97]
37Guy Kortsarz [77] [88]
38Robert Krauthgamer [88]
39Amit Kumar [76]
40Krishnan Kumaran [27] [35]
41Keshav Kunal [93] [99] [102]
42Jens Lagergren [15] [17]
43Insup Lee [55]
44Li Li [75]
45Vincenzo Liberatore [24] [39]
46Nathan Linial [6] [42]
47B. Madan [5]
48Kurt Maly [3] [4] [5]
49Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu) [37]
50Andrew McGregor [79]
51Ioannis Milis [37]
52Rajeev Motwani [7] [9] [13] [14] [19] [22] [23] [28]
53Ravi Mukkamala [3] [4] [5]
54S. Muthukrishnan [21] [26]
55Joseph Naor (Seffi Naor) [43] [51] [52] [62] [64] [69] [77] [84] [88] [91]
56C. Michael Overstreet [3] [4] [5]
57Alessandro Panconesi [15] [17]
58Frank Paterra [4]
59Mike Paterson [26]
60Fernando Pereira [75]
61Benjamin C. Pierce [99] [102]
62Maurice Queyranne [37]
63Rajmohan Rajaraman [30] [31] [63] [66]
64Danny Raz [62]
65José D. P. Rolim [86]
66Dana Ron [86]
67Adi Rosén [31] [66]
68Shmuel Safra [6] [42]
69Baruch Schieber [19] [28]
70Alan Schmitt [99]
71Y. S. Sekhar [3]
72F. Bruce Shepherd [30] [43] [63] [78] [85] [90] [95]
73Insik Shin [55]
74Steven Skiena [21]
75Martin Skutella [37]
76John R. Spletzer [89]
77Aravind Srinivasan [72]
78Clifford Stein [37]
79Madhu Sudan [7] [9] [10] [11] [12] [18] [20] [22] [38]
80Maxim Sviridenko [37]
81Keishi Tajima [60] [73]
82Kunal Talwar [101]
83Kaijun Tan [82]
84Wang Chiew Tan [48] [54] [56] [60] [61] [73]
85Camillo J. Taylor [89]
86Ramakrishna Thurimella (Ramki Thurimella) [45]
87Luca Trevisan [10] [20] [38]
88Umesh V. Vazirani [7] [9] [22]
89Santosh S. Venkatesh [82]
90Mirkó Visontai [98]
91Li-San Wang [74]
92David P. Williamson [11] [18] [38]
93Randall H. Wilson [14] [23]
94Mihalis Yannakakis [30] [63]
95Ramesh Yerraballi [5]
96Francis Zane [44]
97Lisa Zhang [92]
98Shiyu Zhou [25] [40] [55]
99An Zhu [45] [50]
100Leonid Zosin [52] [69]
101Mohammad Zubair [3]

Colors in the list of coauthors

DBLP: [Home | Search: Author, Title | Conferences | Journals]
Michael Ley (ley@uni-trier.de) Thu Dec 27 04:59:51 2007