Samir Khuller - Publications

Affiliations: 
Computer Science University of Maryland, College Park, College Park, MD 
Area:
Theoretical Computer Science,Big Data

102 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Khuller S, Purohit M, Sarpatwar KK. Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems Siam Journal On Discrete Mathematics. 34: 251-270. DOI: 10.1137/18M1212094  0.559
2020 Ahmadi S, Khuller S, Purohit M, Yang S. On Scheduling Coflows Algorithmica. DOI: 10.1007/S00453-020-00741-3  0.306
2019 Khuller S, Li J, Sturmfels P, Sun K, Venkat P. Select and permute: An improved online framework for scheduling to minimize weighted completion time Theoretical Computer Science. 795: 420-431. DOI: 10.1016/J.Tcs.2019.07.026  0.431
2019 Khuller S, Yang S. Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm Algorithmica. 81: 2592-2605. DOI: 10.1007/S00453-019-00545-0  0.487
2018 Murray R, Khuller S, Chao MC. Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms Algorithmica. 80: 2777-2798. DOI: 10.1007/S00453-017-0345-X  0.488
2017 Chang J, Khuller S, Mukherjee K. LP rounding and combinatorial algorithms for minimizing active and busy time Journal of Scheduling. 20: 657-680. DOI: 10.1007/S10951-017-0531-3  0.692
2016 Khuller S, Saha B, Sarpatwar KK. New Approximation Results for Resource Replication Problems Algorithmica. 74: 969-991. DOI: 10.1007/S00453-015-9978-9  0.747
2014 Arora S, Gupta N, Khuller S, Sabharwal Y, Singhal S. Facility location with red-blue demands Operations Research Letters. 42: 462-465. DOI: 10.1016/J.Orl.2014.08.002  0.456
2013 Golubchik L, Khuller S, Mukherjee K, Yao Y. To send or not to send: Reducing the cost of data transmission Proceedings - Ieee Infocom. 2472-2480. DOI: 10.1109/INFCOM.2013.6567053  0.339
2013 Chang J, Gabow HN, Khuller S. A Model for Minimizing Active Processor Time Algorithmica. 1-38. DOI: 10.1007/S00453-013-9807-Y  0.484
2012 Khuller S. Algorithms column: An overview of the recent progress on matrix multiplication by Virginia Vassilevska Williams Sigact News. 43: 57-59. DOI: 10.1145/2421119.2421134  0.386
2012 Khuller S, Kim Y, Malekian A. Improved Approximation Algorithms for Data Migration Algorithmica. 63: 347-362. DOI: 10.1007/S00453-011-9534-1  0.79
2012 Bortnikov E, Khuller S, Li J, Mansour Y, Naor JS. The Load-Distance Balancing Problem Networks. 59: 22-29. DOI: 10.1002/Net.20477  0.542
2011 Chang J, Erlebach T, Gailis R, Khuller S. Broadcast scheduling: Algorithms and complexity Acm Transactions On Algorithms. 7: 47. DOI: 10.1145/2000807.2000815  0.581
2011 Khuller S, Malekian A, Mestre J. To fill or not to fill: The gas station problem Acm Transactions On Algorithms. 7: 36. DOI: 10.1145/1978782.1978791  0.761
2011 Kashyap A, Khuller S, Shayman M. Relay placement for fault tolerance in wireless networks in higher dimensions Computational Geometry: Theory and Applications. 44: 206-215. DOI: 10.1016/J.Comgeo.2010.11.002  0.445
2011 Deshpande A, Khuller S, Malekian A, Toossi M. Energy Efficient Monitoring in Sensor Networks Algorithmica. 59: 94-114. DOI: 10.1007/S00453-010-9407-Z  0.749
2011 Chekuri C, Gal A, Im S, Khuller S, Li J, McCutchen R, Moseley B, Raschid L. New models and algorithms for throughput maximization in broadcast scheduling (extended abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6534: 71-82. DOI: 10.1007/978-3-642-18318-8_7  0.436
2010 Aggarwal G, Feder T, Kenthapadi K, Khuller S, Panigrahy R, Thomas D, Zhu A. Achieving anonymity via clustering Acm Transactions On Algorithms. 6. DOI: 10.1145/1798596.1798602  0.313
2010 Khuller S, Kim Y, Wan YJ. Broadcasting on Networks of Workstations Algorithmica. 57: 848-868. DOI: 10.1007/S00453-008-9249-0  0.629
2010 Saha B, Hoch A, Khuller S, Raschid L, Zhang XN. Dense subgraphs with restrictions and applications to gene annotation graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6044: 456-472. DOI: 10.1007/978-3-642-12683-3_30  0.361
2008 Lee S, Bhattacharjee B, Srinivasan A, Khuller S. Efficient and Resilient Backbones for Multihop Wireless Networks Ieee Transactions On Mobile Computing. 7: 1349-1362. DOI: 10.1109/Tmc.2008.69  0.341
2007 Kashyap A, Lee K, Kalantari M, Khuller S, Shayman M. Integrated topology control and routing in wireless optical mesh networks Computer Networks. 51: 4237-4251. DOI: 10.1016/J.Comnet.2007.05.006  0.411
2007 Khuller S, Martinez MV, Nau D, Sliva A, Simari GI, Subrahmanian VS. Computing most probable worlds of action probabilistic logic programs: Scalable estimation for 1030,000 worlds Annals of Mathematics and Artificial Intelligence. 51: 295-331. DOI: 10.1007/S10472-008-9089-2  0.464
2007 Guha S, Khuller S. Approximation Algorithms for Connected Dominating Sets Algorithmica. 49: 79-79. DOI: 10.1007/S00453-007-9015-8  0.573
2007 Khuller S, Kim Y. Broadcasting in Heterogeneous Networks Algorithmica. 48: 1-21. DOI: 10.1007/S00453-006-1227-9  0.671
2006 Gandhi R, Khuller S, Parthasarathy S, Srinivasan A. Dependent rounding and its applications to approximation algorithms Journal of the Acm. 53: 324-360. DOI: 10.1145/1147954.1147956  0.693
2006 Kashyap A, Khuller S, Shayman M. Relay placement for higher order connectivity in wireless sensor networks Proceedings - Ieee Infocom. DOI: 10.1109/INFOCOM.2006.273  0.319
2006 Gandhi R, Halperin E, Khuller S, Kortsarz G, Srinivasan A. An improved approximation algorithm for vertex cover with hard capacities Journal of Computer and System Sciences. 72: 16-33. DOI: 10.1016/J.Jcss.2005.06.004  0.74
2006 Khuller S, Kim Y, Wan Y(. On generalized gossiping and broadcasting Journal of Algorithms. 59: 81-106. DOI: 10.1016/J.Jalgor.2005.01.002  0.62
2006 Banerjee S, Kommareddy C, Kar K, Bhattacharjee B, Khuller S. OMNI: An efficient overlay multicast infrastructure for real-time applications Computer Networks. 50: 826-841. DOI: 10.1016/J.Comnet.2005.07.023  0.402
2006 Rohloff KR, Khuller S, Kortsarz G. Approximating the Minimal Sensor Selection for Supervisory Control Discrete Event Dynamic Systems. 16: 143-170. DOI: 10.1007/S10626-006-6187-3  0.542
2006 Golubchik L, Khuller S, Kim YA, Shargorodskaya S, Wan YC. Data migration on parallel disks: Algorithms and evaluation Algorithmica (New York). 45: 137-158. DOI: 10.1007/S00453-005-1194-6  0.704
2006 Bleiholder J, Khuller S, Naumann F, Raschid L, Wu Y. Query planning in the presence of overlapping sources Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3896: 811-828. DOI: 10.1007/11687238_48  0.363
2006 Gandhi R, Khuller S, Srinivasan A, Wang N. Approximation algorithms for channel allocation problems in broadcast networks Networks. 47: 225-236. DOI: 10.1002/Net.V47:4  0.67
2006 Gandhi R, Khuller S, Srinivasan A, Wang N. Approximation algorithms for channel allocation problems in broadcast networks Networks. 47: 225-236. DOI: 10.1002/net.20111  0.384
2005 Khuller S. Problems column Acm Transactions On Algorithms. 1: 130-134. DOI: 10.1145/1077464.1077475  0.449
2004 Khuller S, Kim Y. Algorithms for Data Migration with Cloning Siam Journal On Computing. 33: 448-461. DOI: 10.1137/S009753970342585X  0.718
2004 Cheng WC, Chou CF, Golubchik L, Khuller S, Wan YC. A coordinated data collection approach: Design, evaluation, and comparison Ieee Journal On Selected Areas in Communications. 22: 2004-2018. DOI: 10.1109/Jsac.2004.836009  0.399
2004 Khuller S, Kim Y. Equivalence of two linear programming relaxations for broadcast scheduling Operations Research Letters. 32: 473-478. DOI: 10.1016/J.Orl.2003.11.012  0.628
2004 Gandhi R, Khuller S, Srinivasan A. Approximation algorithms for partial covering problems Journal of Algorithms. 53: 55-84. DOI: 10.1016/J.Jalgor.2004.04.002  0.66
2004 Gandhi R, Khuller S, Kim Y, Wan Y(. Algorithms for Minimizing Response Time in Broadcast Scheduling Algorithmica. 38: 597-608. DOI: 10.1007/S00453-003-1058-X  0.742
2003 Golubchik L, Cheng WC, Chou C, Khuller S, Samet H, Wan CJ. Bistro: a scalable and secure data transfer service for digital government applications Communications of the Acm. 46: 50-51. DOI: 10.1145/602421.602448  0.303
2003 Khuller S, Bhatia R, Pless R. On Local Search and Placement of Meters in Networks Siam Journal On Computing. 32: 470-487. DOI: 10.1137/S0097539799363359  0.585
2003 Kashyap S, Khuller S. Algorithms for non-uniform size data placement on parallel disks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2914: 265-276. DOI: 10.1016/J.Jalgor.2004.06.007  0.714
2002 Khuller S. Algorithms column: the vertex cover problem Sigact News. 33: 31-33. DOI: 10.1145/564585.564598  0.556
2002 Charikar M, Khuller S, Raghavachari B. Algorithms for capacitated vehicle routing Siam Journal On Computing. 31: 665-682. DOI: 10.1137/S0097539701392056  0.499
2002 Khuller S, Zhu A. The General Steiner Tree-Star problem Information Processing Letters. 84: 215-220. DOI: 10.1016/S0020-0190(02)00271-5  0.521
2001 Khuller S. Algorithms column Sigact News. 32: 28-31. DOI: 10.1145/504192.504193  0.418
2001 Ben-Yashar R, Khuller S, Kraus S. Optimal collective dichotomous choice under partial order constraints Mathematical Social Sciences. 41: 349-364. DOI: 10.1016/S0165-4896(00)00069-X  0.448
2000 Golubchik L, Khanna S, Khuller S, Thurimella R, Zhu A. Approximation algorithms for data placement on parallel disks Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 223-232. DOI: 10.1145/1597036.1597037  0.491
2000 Khuller S, Sussmann YJ. The Capacitated K -Center Problem Siam Journal On Discrete Mathematics. 13: 403-418. DOI: 10.1137/S0895480197329776  0.572
2000 Khuller S, Pless R, Sussmann YJ. Fault tolerant K -center problems Theoretical Computer Science. 242: 237-245. DOI: 10.1016/S0304-3975(98)00222-9  0.552
2000 Khuller S, Rosenfeld A, Wu A. Centers of sets of pixels Discrete Applied Mathematics. 103: 297-306. DOI: 10.1016/S0166-218X(99)00248-6  0.314
2000 Khuller S. Addendum to “An O(|V|2) algorithm for single connectedness”, [Information Processing Letters 72 (3–4) (1999) 105–107] Information Processing Letters. 74: 263. DOI: 10.1016/S0020-0190(00)00054-5  0.341
2000 Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B. Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem Algorithmica. 28: 422-437. DOI: 10.1007/S004530010045  0.516
2000 Bhatia R, Khuller S, Naor J(. The Loading Time Scheduling Problem Journal of Algorithms. 36: 1-33. DOI: 10.1006/Jagm.2000.1076  0.534
2000 Bhatia R, Khuller S, Pless R, Sussmann YJ. The full‐degree spanning tree problem Networks. 36: 203-209. DOI: 10.1002/1097-0037(200012)36:4<203::Aid-Net1>3.0.Co;2-U  0.602
1999 Khuller S. An O(|V|2) algorithm for single connectedness Information Processing Letters. 72: 105-107. DOI: 10.1016/S0020-0190(99)00135-0  0.383
1999 Khuller S, Moss A, Naor J(. The budgeted maximum coverage problem Information Processing Letters. 70: 39-45. DOI: 10.1016/S0020-0190(99)00031-9  0.478
1999 Guha S, Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms Journal of Algorithms. 31: 228-248. DOI: 10.1006/jagm.1998.0993  0.329
1999 Khuller S, Agarwal PK, O'Rourke J. Open Problems Presented at SCG'98 Journal of Algorithms. 30: 449-453. DOI: 10.1006/Jagm.1998.0979  0.469
1999 Guha S, Khuller S. Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets Information and Computation. 150: 57-74. DOI: 10.1006/Inco.1998.2754  0.519
1998 Khuller S. Open problems Acm Sigact News. 29: 15-17. DOI: 10.1145/281068.281073  0.365
1998 Bhatia R, Guha S, Khuller S, Sussmann YJ. Journal of Combinatorial Optimization. 2: 199-217. DOI: 10.1023/A:1009796525600  0.474
1998 Guha S, Khuller S. Approximation Algorithms for Connected Dominating Sets Algorithmica. 20: 374-387. DOI: 10.1007/PL00009201  0.377
1998 Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B. Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem (Extended Abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1530: 6-17. DOI: 10.1007/978-3-540-49382-2_2  0.426
1997 Khuller S. Open problems Acm Sigact News. 28: 33-36. DOI: 10.1145/262301.262308  0.365
1997 Fekete SP, Khuller S, Klemmstein M, Raghavachari B, Young N. A network-flow technique for finding low-weight bounded-degree spanning trees Journal of Algorithms. 24: 310-324. DOI: 10.1006/Jagm.1997.0862  0.518
1996 Khuller S. Open Problems 14 Acm Sigact News. 27: 11. DOI: 10.1145/242581.571625  0.365
1996 Khuller S. Open Problems: 13 Acm Sigact News. 27: 52-54. DOI: 10.1145/235767.571634  0.365
1996 Khuller S, Raghavachari B. Graph and network algorithms Acm Computing Surveys. 28: 43-45. DOI: 10.1145/234313.234334  0.492
1996 Khuller S, Raghavachari B, Young N. Low-Degree Spanning Trees of Small Weight Siam Journal On Computing. 25: 355-368. DOI: 10.1137/S0097539794264585  0.41
1996 Khuller S, Raghavachari B, Rosenfeld A. Landmarks in graphs Discrete Applied Mathematics. 70: 217-229. DOI: 10.1016/0166-218X(95)00106-2  0.372
1996 Khuller S, Raghavachari B, Young N. On strongly connected digraphs with bounded cycle length Discrete Applied Mathematics. 69: 281-289. DOI: 10.1016/0166-218X(95)00105-Z  0.485
1996 Khuller S, Raghavachari B. Improved Approximation Algorithms for Uniform Connectivity Problems Journal of Algorithms. 21: 434-450. DOI: 10.1006/Jagm.1996.0052  0.609
1996 Khuller S, Raghavachari B, Young N. On strongly connected digraphs with bounded cycle length Discrete Applied Mathematics. 69: 281-289.  0.359
1996 Khuller S, Raghavachari B. Graph and network algorithms Acm Computing Surveys. 28: 42-45.  0.343
1996 Fekete SP, Khuller S, Klemmstein M, Raghavachari B, Young N. A network-flow technique for finding low-weight bounded-degree spanning trees Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1084: 105-117.  0.428
1995 Khuller S. Open Problems: 11 Acm Sigact News. 26: 33. DOI: 10.1145/203610.606408  0.365
1995 Khuller S, Raghavachari B, Young N. Approximating the Minimum Equivalent Digraph Siam Journal On Computing. 24: 859-872. DOI: 10.1137/S0097539793256685  0.621
1995 Khuller S, Raghavachari B, Young N. Balancing minimum spanning trees and shortest-path trees Algorithmica. 14: 305-321. DOI: 10.1007/Bf01294129  0.449
1995 Aggarwal A, Bar-Noy A, Khuller S, Kravets D, Schieber B. Efficient minimum cost matching and transportation using the quadrangle inequality Journal of Algorithms. 19: 116-143. DOI: 10.1006/Jagm.1995.1030  0.479
1995 Khuller S, Matias Y. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem Information & Computation. 118: 34-37. DOI: 10.1006/Inco.1995.1049  0.553
1994 Khuller S, Mitchell SG, Vazirani VV. On-line algorithms for weighted bipartite matching and stable marriages Theoretical Computer Science. 127: 255-267. DOI: 10.1016/0304-3975(94)90042-6  0.372
1994 Khuller S, Raghavachari B, Young N. Designing multi-commodity flow trees Information Processing Letters. 50: 49-55. DOI: 10.1016/0020-0190(94)90044-2  0.489
1994 Khuller S, Vishkin U. On the parallel complexity of digraph reachability Information Processing Letters. 52: 239-241. DOI: 10.1016/0020-0190(94)00153-7  0.591
1994 Khuller S, Vishkin U, Young N. A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers Journal of Algorithms. 17: 280-289. DOI: 10.1006/Jagm.1994.1036  0.505
1993 Khuller S, Naor J(, Klein P. The Lattice Structure of Flow in Planar Graphs Siam Journal On Discrete Mathematics. 6: 477-490. DOI: 10.1137/0406038  0.44
1993 Arkin EM, Khuller S, Mitchell JSB. Geometric knapsack problems Algorithmica. 10: 399-427. DOI: 10.1007/Bf01769706  0.553
1993 Khuller S, Thurimella R. Approximation Algorithms for Graph Augmentation Journal of Algorithms. 14: 214-225. DOI: 10.1006/Jagm.1993.1010  0.5
1992 Khuller S, Vishkin U. Biconnectivity approximations and graph carvings Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 759-770. DOI: 10.1145/174652.174654  0.548
1992 Khuller S, Mitchell SG, Vazirani VV. Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph Siam Journal On Computing. 21: 486-506. DOI: 10.1137/0221032  0.546
1992 Khuller S, Schieber B. On independent spanning trees Information Processing Letters. 42: 321-323. DOI: 10.1016/0020-0190(92)90230-S  0.352
1991 Khuller S, Schieber B. Efficient parallel algorithms for testing k -connectivity and finding disjoint s-t paths in graphs Siam Journal On Computing. 20: 352-375. DOI: 10.1137/0220022  0.49
1991 Khuller S, Vazirani VV. Planar graph coloring is not self-reducible, assuming P ≠ NP Theoretical Computer Science. 88: 183-189. DOI: 10.1016/0304-3975(91)90081-C  0.357
1990 Khuller S. Open problems Acm Sigact News. 21: 12. DOI: 10.1145/379139.379163  0.365
1990 Khuller S. Extending planar graph algorithms to K 3,3 -free graphs Information & Computation. 84: 13-25. DOI: 10.1016/0890-5401(90)90031-C  0.512
1990 Khuller S, Mitchell JSB. On a triangle counting problem Information Processing Letters. 33: 319-321. DOI: 10.1016/0020-0190(90)90217-L  0.512
1990 Khuller S. Coloring algorithms for K 5 -minor free graphs Information Processing Letters. 34: 203-208. DOI: 10.1016/0020-0190(90)90161-P  0.46
1989 Khuller S. Open problems: 3 Acm Sigact News. 20: 24-24. DOI: 10.1145/74074.74078  0.365
1989 Khuller S. On computing graph closures Information Processing Letters. 31: 249-255. DOI: 10.1016/0020-0190(89)90082-3  0.387
Show low-probability matches.