Sudipto Guha

2008
87	EE	Sudipto Guha, Hyoungmin Park, Kyuseok Shim: Wavelet synopsis for hierarchical range queries with workloads. VLDB J. accepted for publication: (2008)
2007
86	EE	Sudipto Guha, Piotr Indyk, Andrew McGregor: Sketching Information Divergences. COLT 2007: 424-438
85	EE	Sudipto Guha, Andrew McGregor: Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming. ICALP 2007: 704-715
84	EE	Sudipto Guha, Kamesh Munagala: Model-driven optimization using adaptive probes. SODA 2007: 308-317
83	EE	Sudipto Guha, Kamesh Munagala: Approximation algorithms for budgeted learning problems. STOC 2007: 104-113
82	EE	Sudipto Guha, Boulos Harb: Nonlinear Approximation and Image Representation using Wavelets. Web Information Retrieval and Linear Algebra Algorithms 2007
81	EE	Sudipto Guha, Kamesh Munagala, Peng Shi: On Index Policies for Restless Bandit Problems CoRR abs/0711.3861: (2007)
80	EE	Sudipto Guha, Kyuseok Shim: A Note on Linear Time Algorithms for Maximum Error Histograms. IEEE Trans. Knowl. Data Eng. 19(7): 993-997 (2007)
2006
79	EE	Sudipto Guha, Nick Koudas, Divesh Srivastava, Xiaohui Yu: Reasoning About Approximate Match Query Results. ICDE 2006: 8
78	EE	Ashish Goel, Sudipto Guha, Kamesh Munagala: Asking the right questions: model-driven optimization using probes. PODS 2006: 203-212
77	EE	Sudipto Guha, Andrew McGregor: Approximate quantiles and the order of the stream. PODS 2006: 273-279
76	EE	Sudipto Guha, Kamesh Munagala, Saswati Sarkar: Optimizing transmission rate in wireless channels using adaptive probes. SIGMETRICS/Performance 2006: 381-382
75	EE	Sudipto Guha, Boulos Harb: Approximation algorithms for wavelet transform coding of data streams. SODA 2006: 698-707
74	EE	Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian: Streaming and sublinear approximation of entropy and information distances. SODA 2006: 733-742
73	EE	Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu: Integrating XML data sources using approximate joins. ACM Trans. Database Syst. 31(1): 161-207 (2006)
72	EE	Sudipto Guha, Nick Koudas, Kyuseok Shim: Approximation and streaming algorithms for histogram construction problems. ACM Trans. Database Syst. 31(1): 396-438 (2006)
71	EE	Sudipto Guha, Boulos Harb: Approximation algorithms for wavelet transform coding of data streams CoRR abs/cs/0604097: (2006)
70	EE	Chandra Chekuri, Sudipto Guha, Joseph Naor: The Steiner k-Cut Problem. SIAM J. Discrete Math. 20(1): 261-271 (2006)
2005
69	EE	Sudipto Guha, Boulos Harb: Wavelet synopsis for data streams: minimizing non-euclidean error. KDD 2005: 88-97
68	EE	Sudipto Guha, Kyuseok Shim: Offline and Data Stream Algorithms for Efficient Computation of Synopsis Structures. VLDB 2005: 1364
67	EE	Sudipto Guha: Space Efficiency in Synopsis Construction Algorithms. VLDB 2005: 409-420
66	EE	Sudipto Guha: How far will you walk to find your shortcut: Space Efficient Synopsis Construction Algorithms CoRR abs/cs/0502075: (2005)
65	EE	Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian: Streaming and Sublinear Approximation of Entropy and Information Distances CoRR abs/cs/0508122: (2005)
64	EE	Julia 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)
63	EE	Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34(4): 803-824 (2005)
2004
62	EE	Tugkan Batu, Sudipto Guha, Sampath Kannan: Inferring Mixtures of Markov Chains. COLT 2004: 186-199
61	EE	Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90
60	EE	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. STOC 2004: 21-27
59	EE	Sudipto Guha, Chulyun Kim, Kyuseok Shim: XWAVE: Approximate Extended Wavelets for Streaming Data. VLDB 2004: 288-299
58	EE	Sudipto Guha, Kyuseok Shim, Jungchul Woo: REHIST: Relative Error Histogram Construction Algorithms. VLDB 2004: 300-311
57	EE	Sudipto Guha, Nick Koudas, Amit Marathe, Divesh Srivastava: Merging the Results of Approximate Match Operations. VLDB 2004: 636-647
2003
56	EE	Rajeev Alur, Swarat Chaudhuri, Kousha Etessami, Sudipto Guha, Mihalis Yannakakis: Compression of Partially Ordered Strings. CONCUR 2003: 42-56
55	EE	Chandra Chekuri, Sudipto Guha, Joseph Naor: Approximating Steiner k-Cuts. ICALP 2003: 189-199
54	EE	Sudipto Guha, Nick Koudas, Divesh Srivastava, Ting Yu: Index-Based Approximate XML Joins. ICDE 2003: 708-710
53	EE	Sudipto Guha, Dimitrios Gunopulos, Nick Koudas: Correlating synchronous and asynchronous data streams. KDD 2003: 529-534
52	EE	Sudipto Guha, Shankar Krishnan, Kamesh Munagala, Suresh Venkatasubramanian: Application of the two-sided depth test to CSG rendering. SI3D 2003: 177-180
51	EE	Sudipto Guha, Dimitrios Gunopulos, Nick Koudas, Divesh Srivastava, Michail Vlachos: Efficient Approximation Of Optimization Queries Under Parametric Aggregation Constraints. VLDB 2003: 778-789
50		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: Techniques for Clustering Massive Data Sets. Clustering and Information Retrieval 2003: 35-82
49	EE	Sudipto Guha, Athina Markopoulou, Fouad A. Tobagi: Hierarchical Reliable Multicast: Performance Analysis and Optimal Placement of Proxies. Computer Communications 26(18): 2070-2081 (2003)
48	EE	Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Asymmetric k-center is log*n-hard to Approximate Electronic Colloquium on Computational Complexity (ECCC)(038): (2003)
47	EE	Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams: Theory and Practice. IEEE Trans. Knowl. Data Eng. 15(3): 515-528 (2003)
46	EE	Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or: Capacitated vertex covering. J. Algorithms 48(1): 257-270 (2003)
45	EE	Sudipto Guha, Adam Meyerson, Kamesh Munagala: A constant factor approximation algorithm for the fault-tolerant facility location problem. J. Algorithms 48(2): 429-440 (2003)
2002
44	EE	Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Histogramming Data Streams with Fast Per-Item Processing. ICALP 2002: 681-692
43	EE	Sudipto Guha, Nick Koudas: Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation. ICDE 2002: 567-
42	EE	Liadan O'Callaghan, Adam Meyerson, Rajeev Motwani, Nina Mishra, Sudipto Guha: Streaming-Data Algorithms for High-Quality Clustering. ICDE 2002: 685-
41	EE	Sudipto Guha, Nick Koudas, Divesh Srivastava: Fast Algorithms For Hierarchical Range Histogram Construction. PODS 2002: 180-187
40	EE	Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu: Approximate XML joins. SIGMOD Conference 2002: 287-298
39	EE	Nitin Thaper, Sudipto Guha, Piotr Indyk, Nick Koudas: Dynamic multidimensional histograms. SIGMOD Conference 2002: 428-439
38	EE	Sudipto Guha, Kamesh Munagala: Improved algorithms for the data placement problem. SODA 2002: 106-107
37	EE	Sudipto Guha, Kamesh Munagala: Generalized clustering. SODA 2002: 484-485
36	EE	Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai: Throughput maximization of real-time scheduling with batching. SODA 2002: 742-751
35	EE	Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or: Capacitated vertex covering with applications. SODA 2002: 858-865
34	EE	Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Near-optimal sparse fourier representations via sampling. STOC 2002: 152-161
33	EE	Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss: Fast, small-space algorithms for approximate histogram maintenance. STOC 2002: 389-398
32	EE	Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci. 65(1): 129-149 (2002)
31	EE	Guy Even, Sudipto Guha, Baruch Schieber: Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. SIAM J. Comput. 32(1): 231-252 (2002)
2001
30	EE	Sudipto Guha, Adam Meyerson, Kamesh Munagala: Improved algorithms for fault tolerant facility location. SODA 2001: 636-641
29	EE	Sudipto Guha, Adam Meyerson, Kamesh Munagala: A constant factor approximation for the single sink edge installation problems. STOC 2001: 383-388
28	EE	Sudipto Guha, Nick Koudas, Kyuseok Shim: Data-streams and histograms. STOC 2001: 471-475
27	EE	Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: Cure: An Efficient Clustering Algorithm for Large Databases. Inf. Syst. 26(1): 35-58 (2001)
26	EE	Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput. 31(2): 331-352 (2001)
2000
25		Sudipto Guha: Nested Graph Dissection and Approximation Algorithms. FOCS 2000: 126-135
24		Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams. FOCS 2000: 359-366
23		Sudipto Guha, Adam Meyerson, Kamesh Munagala: Hierarchical Placement and Network Design Problems. FOCS 2000: 603-612
22	EE	Guy Even, Sudipto Guha, Baruch Schieber: Improved approximations of crossings in graph drawings. STOC 2000: 296-305
21	EE	Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes. Inf. Syst. 25(5): 345-366 (2000)
20		Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Message Multicasting in Heterogeneous Networks. SIAM J. Comput. 30(2): 347-358 (2000)
1999
19	EE	Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. FOCS 1999: 378-388
18	EE	Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes. ICDE 1999: 512-521
17	EE	Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). STOC 1999: 1-10
16	EE	Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber: Efficient Recovery from Power Outage (Extended Abstract). STOC 1999: 574-582
15	EE	Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. STOC 1999: 622-631
14		Sudipto Guha, Samir Khuller: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. Inf. Comput. 150(1): 57-74 (1999)
13		Sudipto Guha, Samir Khuller: Greedy Strikes Back: Improved Facility Location Algorithms. J. Algorithms 31(1): 228-248 (1999)
12		Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. J. Algorithms 33(1): 73-91 (1999)
1998
11	EE	Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin: Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 1998: 379-388
10		Sudipto Guha, Samir Khuller: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. FSTTCS 1998: 54-65
9	EE	Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998: 73-84
8		Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. SODA 1998: 192-200
7		Sudipto Guha, Samir Khuller: Greedy Strikes Back: Improved Facility Location Algorithms. SODA 1998: 649-657
6	EE	Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha: Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. STOC 1998: 114-123
5	EE	Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Multicasting in Heterogeneous Networks. STOC 1998: 448-453
4	EE	Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann: Facility Location with Dynamic Distance Function (Extended Abstract). SWAT 1998: 23-34
3		Sudipto Guha, Samir Khuller: Approximation Algorithms for Connected Dominating Sets. Algorithmica 20(4): 374-387 (1998)
2		Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann: Facility Location with Dynamic Distance Functions. J. Comb. Optim. 2(3): 199-217 (1998)
1996
1		Sudipto Guha, Samir Khuller: Approximation Algorithms for Connected Dominating Sets. ESA 1996: 179-193

Coauthor Index

1	Rajeev Alur	[56]
2	Amotz Bar-Noy	[5] [15] [20] [26] [36]
3	Tugkan Batu	[62]
4	Randeep Bhatia	[2] [4]
5	Moses Charikar	[6] [8] [11] [12] [17] [19] [32] [63]
6	Swarat Chaudhuri	[56]
7	Chandra Chekuri	[6] [8] [11] [12] [55] [70]
8	To-Yat Cheung	[8] [12]
9	Julia Chuzhoy	[48] [60] [61] [64]
10	Zuo Dai	[8] [12]
11	Kousha Etessami	[56]
12	Guy Even	[22] [31]
13	Anna C. Gilbert	[33] [34]
14	Ashish Goel	[6] [8] [11] [12] [78]
15	Dimitrios Gunopulos	[51] [53]
16	Eran Halperin	[60] [64]
17	Boulos Harb	[69] [71] [75] [82]
18	Refael Hassin	[35] [46]
19	Piotr Indyk	[33] [34] [39] [44] [86]
20	H. V. Jagadish	[40] [73]
21	Sampath Kannan	[62]
22	Yoav Katz	[36]
23	Sanjeev Khanna	[48] [60] [61] [64]
24	Samir Khuller	[1] [2] [3] [4] [7] [10] [13] [14] [35] [46]
25	Chulyun Kim	[59]
26	Guy Kortsarz	[60] [64]
27	Yannis Kotidis	[33]
28	Nick Koudas	[28] [39] [40] [41] [43] [51] [53] [54] [57] [72] [73] [79]
29	Robert Krauthgamer	[64]
30	Shankar Krishnan	[52]
31	Ming Li	[8] [12]
32	Amit Marathe	[57]
33	Athina Markopoulou	[49]
34	Andrew McGregor	[65] [74] [77] [85] [86]
35	Adam Meyerson	[23] [29] [30] [42] [45] [47]
36	Nina Mishra	[24] [42] [47]
37	Anna Moss	[16]
38	Rajeev Motwani	[24] [42] [47]
39	Kamesh Munagala	[23] [29] [30] [37] [38] [45] [52] [76] [78] [81] [83] [84]
40	S. Muthukrishnan	[33] [34] [44]
41	Joseph Naor (Seffi Naor)	[5] [15] [16] [20] [26] [36] [48] [55] [60] [61] [64] [70]
42	Liadan O'Callaghan	[24] [42] [47]
43	Einat Or	[35] [46]
44	Hyoungmin Park	[87]
45	Serge A. Plotkin	[11]
46	Rajeev Rastogi	[9] [18] [21] [27] [50]
47	Saswati Sarkar	[76]
48	Baruch Schieber	[5] [15] [16] [20] [22] [26] [31] [36]
49	Hadas Shachnai	[36]
50	Peng Shi	[81]
51	Kyuseok Shim	[9] [18] [21] [27] [28] [50] [58] [59] [68] [72] [80] [87]
52	David B. Shmoys	[17] [32]
53	Divesh Srivastava	[40] [41] [51] [54] [57] [73] [79]
54	Martin Strauss (Martin J. Strauss)	[33] [34] [44]
55	Yoram J. Sussmann	[2] [4]
56	Éva Tardos	[17] [32]
57	Nitin Thaper	[39]
58	Fouad A. Tobagi	[49]
59	Suresh Venkatasubramanian	[52] [65] [74]
60	Michail Vlachos	[51]
61	Jungchul Woo	[58]
62	Mihalis Yannakakis	[56]
63	Ting Yu	[40] [54] [73]
64	Xiaohui Yu	[79]

Colors in the list of coauthors