☰

Kirk Pruhs - Publications

Affiliations: 
University of Pittsburgh, Pittsburgh, PA, United States 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

75 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
2016 Kaklamanis C, Pruhs K. Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms Theory of Computing Systems. 58: 1-3. DOI: 10.1007/s00224-015-9619-3  0.342
2016 Antoniadis A, Barcelo N, Nugent M, Pruhs K, Schewior K, Scquizzato M. Chasing convex bodies and functions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9644: 68-81. DOI: 10.1007/978-3-662-49529-2_6  0.388
2015 Im S, Moseley B, Pruhs K. Stochastic scheduling of heavy-tailed jobs Leibniz International Proceedings in Informatics, Lipics. 30: 474-486. DOI: 10.4230/LIPIcs.STACS.2015.474  0.384
2015 Bansal N, Gupta A, Krishnaswamy R, Pruhs K, Schewior K, Stein C. A 2-competitive algorithm for online convex optimization with switching costs Leibniz International Proceedings in Informatics, Lipics. 40: 96-109. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.96  0.323
2015 Barcelo N, Kling P, Nugent M, Pruhs K, Scquizzato M. On the complexity of speed scaling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9235: 75-89. DOI: 10.1007/978-3-662-48054-0_7  0.425
2015 Antoniadis A, Barcelo N, Nugent M, Pruhs K, Scquizzato M. A o(n)-competitive deterministic algorithm for online matching on a line Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8952: 11-22. DOI: 10.1007/978-3-319-18263-6_2  0.369
2014 Antoniadis A, Barcelo N, Consuegra M, Kling P, Nugent M, Pruhs K, Scquizzatok M. Efficient computation of optimal energy and fractional weighted flow trade-off schedules Leibniz International Proceedings in Informatics, Lipics. 25: 63-74. DOI: 10.4230/LIPIcs.STACS.2014.63  0.405
2014 Im S, Moseley B, Pruhs K, Torng E. Competitively scheduling tasks with intermediate parallelizability Annual Acm Symposium On Parallelism in Algorithms and Architectures. 22-29. DOI: 10.1145/2612669.2612682  0.375
2014 Krishnaswamy R, Nagarajan V, Pruhs K, Stein C. Cluster before you hallucinate: Approximating node-capacitated network design and energy efficient routing Proceedings of the Annual Acm Symposium On Theory of Computing. 734-743. DOI: 10.1145/2591796.2591831  0.341
2014 Im. S, Moseley B, Pruhs K. Online scheduling with general cost functions Siam Journal On Computing. 43: 126-143. DOI: 10.1137/120902288  0.515
2014 Im S, Kulkarni J, Munagala K, Pruhs K. SelfishMigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 531-540. DOI: 10.1109/FOCS.2014.63  0.455
2013 Bansal N, Chan HL, Pruhs K. Speed scaling with an arbitrary power function Acm Transactions On Algorithms. 9. DOI: 10.1145/2438645.2438650  0.52
2013 Gupta A, Krishnaswamy R, Pruhs K. Online primal-dual for non-linear optimization with applications to speed scaling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7846: 173-186. DOI: 10.1007/978-3-642-38016-7_15  0.395
2012 Bansal N, Pruhs K. Weighted geometric set multi-cover via quasi-uniform sampling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7501: 145-156. DOI: 10.20382/Jocg.V7I1A11  0.401
2012 Edmonds J, Pruhs K. Scalably scheduling processes with arbitrary speedup curves Acm Transactions On Algorithms. 8. DOI: 10.1145/2229163.2229172  0.493
2012 Cole D, Letsios D, Nugent M, Pruhs K. Optimal energy trade-off schedules 2012 International Green Computing Conference, Igcc 2012. DOI: 10.1109/IGCC.2012.6322257  0.336
2012 Cole D, Im S, Moseley B, Pruhs K. Speed scaling for stretch plus energy Operations Research Letters. 40: 180-184. DOI: 10.1016/J.Orl.2012.02.003  0.476
2012 Gupta A, Im S, Krishnaswamy R, Moseley B, Pruhs K. Scheduling heterogeneous processors isn't as easy as you think Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1242-1253.  0.465
2011 Im S, Moseley B, Pruhs K. A tutorial on amortized local competitiveness in online scheduling Sigact News. 42: 83-97. DOI: 10.1145/1998037.1998058  0.46
2011 Gupta A, Krishnaswamy R, Pruhs K. Nonclairvoyantly scheduling power-heterogeneous processors Sustainable Computing: Informatics and Systems. 1: 248-255. DOI: 10.1016/J.Suscom.2011.05.007  0.47
2011 Chung C, Ligett K, Pruhs K, Roth A. The Power of Fair Pricing Mechanisms Algorithmica (New York). 1-11. DOI: 10.1007/S00453-011-9587-1  0.437
2011 Chan HL, Edmonds J, Lam TW, Lee LK, Marchetti-Spaccamela A, Pruhs K. Nonclairvoyant speed scaling for flow and energy Algorithmica (New York). 61: 507-517. DOI: 10.1007/S00453-010-9420-2  0.402
2011 Chan HL, Edmonds J, Pruhs K. Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor Theory of Computing Systems. 49: 817-833. DOI: 10.1007/S00224-011-9349-0  0.462
2011 Pruhs K, Robert J, Schabanel N. Minimizing maximum flowtime of jobs with arbitrary parallelizability Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6534: 237-248. DOI: 10.1007/978-3-642-18318-8_21  0.488
2010 Gupta A, Im S, Krishnaswamy R, Moseley B, Pruhs K. Scheduling jobs with varying parallelizability to reduce variance Annual Acm Symposium On Parallelism in Algorithms and Architectures. 11-20. DOI: 10.1145/1810479.1810482  0.407
2010 Bansal N, Pruhs K. The geometry of scheduling Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 407-414. DOI: 10.1137/130911317  0.51
2010 Bansal N, Pruhs KR. Server scheduling to balance priorities, fairness, and average quality of service Siam Journal On Computing. 39: 3311-3335. DOI: 10.1137/090772228  0.433
2010 Gupta A, Krishnaswamy R, Pruhs K. Nonclairvoyantly scheduling power-heterogeneous processors 2010 International Conference On Green Computing, Green Comp 2010. 165-173. DOI: 10.1109/GREENCOMP.2010.5598311  0.393
2010 Baruah S, Pruhs K. Open problems in real-time scheduling Journal of Scheduling. 13: 577-582. DOI: 10.1007/S10951-009-0137-5  0.432
2010 Pruhs K, Stein C. How to schedule when you have to buy your energy Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 352-365. DOI: 10.1007/978-3-642-15369-3_27  0.399
2010 Gupta A, Krishnaswamy R, Pruhs K. Scalably scheduling power-heterogeneous processors Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6198: 312-323. DOI: 10.1007/978-3-642-14165-2_27  0.357
2009 Bansal N, Chan HL, Pruhs K, Katz D. Improved bounds for speed scaling in devices obeying the cube-root rule Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 144-155. DOI: 10.4086/Toc.2012.V008A009  0.466
2009 Bansal N, Chan HL, Pruhs K. Speed scaling with a solar cell Theoretical Computer Science. 410: 4580-4587. DOI: 10.1016/j.tcs.2009.07.004  0.344
2008 Sharaf MA, Chrysanthis PK, Labrinidis A, Pruhs K. Algorithms and metrics for processing multiple heterogeneous continuous queries Acm Transactions On Database Systems. 33. DOI: 10.1145/1331904.1331909  0.378
2008 Bansal N, Bunde DP, Chan HL, Pruhs K. Average rate speed scaling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4957: 240-251. DOI: 10.1007/S00453-009-9379-Z  0.39
2008 Pruhs K, Van Stee R, Uthaisombut P. Speed scaling of tasks with precedence constraints Theory of Computing Systems. 43: 67-80. DOI: 10.1007/S00224-007-9070-1  0.421
2008 Chung C, Pruhs K, Uthaisombut P. The online transportation problem: On the exponential boost of one extra server Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4957: 228-239.  0.344
2007 Bansal N, Kimbrel T, Pruhs K. Speed scaling to manage energy and temperature Journal of the Acm. 54. DOI: 10.1145/1206035.1206038  0.451
2007 Bansal N, Pruhs K, Stein C. Speed scaling for weighted flow time Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 7: 805-813. DOI: 10.1137/08072125X  0.463
2007 Bansal N, Chan HL, Khandekar R, Pruhs K, Schieber B, Stein C. Non-preemptive min-sum scheduling with resource augmentation Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 614-624. DOI: 10.1109/FOCS.2007.4389530  0.319
2007 Bansal N, Chan HL, Pruhs K. Competitive algorithms for due date scheduling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4596: 28-39. DOI: 10.1007/S00453-009-9321-4  0.536
2006 Edmonds J, Pruhs K. Balanced allocations of cake Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 623-632. DOI: 10.1109/FOCS.2006.17  0.379
2006 Becchetti L, Leonardi S, Marchetti-Spaccamela A, Pruhs K. Online weighted flow time and deadline scheduling Journal of Discrete Algorithms. 4: 339-352. DOI: 10.1016/J.Jda.2005.12.001  0.489
2005 Kalyanasundaram B, Pruhs KR. Fault-tolerant scheduling Siam Journal On Computing. 34: 697-719. DOI: 10.1137/S0097539794261799  0.316
2005 Azar Y, Buchsbaum A, Chazelle B, Cole R, Fleischer L, Golin M, Goodrich M, Grossi R, Guha S, Halldorsson MM, Indyk P, Italiano GF, Kaplan H, Myrvold W, Pruhs K, et al. Proceeding of the Annual ACM-SIAM Symposium on Discrete Algorithms: Preface Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. xiii.  0.349
2005 Bansal N, Pruhs K. Speed scaling to manage temperature Lecture Notes in Computer Science. 3404: 460-471.  0.353
2004 Pruhs K, Uthaisombut P, Woeginger G. Getting the best response for your erg Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3111: 14-25. DOI: 10.1145/1367064.1367078  0.459
2004 Edmonds J, Pruhs K. A Maiden Analysis of Longest Wait First Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 811-820. DOI: 10.1145/1077464.1077467  0.443
2004 Pruhs K, Woeginger GJ. Approximation schemes for a class of subset selection problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2976: 203-211. DOI: 10.1016/J.Tcs.2007.03.006  0.432
2004 Becchetti L, Leonardi S, Marchetti-Spaccamela A, Pruhs K. Semi-clairvoyant scheduling Theoretical Computer Science. 324: 325-335. DOI: 10.1016/J.Tcs.2004.05.023  0.494
2004 Bansal N, Pruhs K. Server scheduling in the weighted ℓp norm Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2976: 434-443.  0.383
2004 Bansal N, Kimbrel T, Pruhs K. Dynamic speed scaling to manage energy and temperature Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 520-529.  0.348
2004 Kohrt JS, Pruhs K. A constant approximation algorithm for sorting buffers Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2976: 193-202.  0.436
2003 Kalyanasundaram B, Pruhs KR. Minimizing flow time nonclairvoyantly Journal of the Acm. 50: 551-567. DOI: 10.1145/792538.792545  0.425
2003 Pruhs K. Journal of Algorithms: Foreword Journal of Algorithms. 48: 1. DOI: 10.1016/S0196-6774(03)00042-7  0.326
2003 Edmonds J, Pruhs K. Multicast pull scheduling: When fairness is fine Algorithmica (New York). 36: 315-330. DOI: 10.1007/S00453-003-1018-5  0.517
2003 Bansal N, Pruhs K. Server scheduling in the Lpnorm: A rising tide lifts all boat Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 242-250.  0.402
2002 Kalyanasundaram B, Noga J, Pruhs KR, Woeginger GJ. Caching for web searching Algorithmica (New York). 33: 353-370. DOI: 10.1007/S00453-001-0123-6  0.426
2002 Edmonds J, Pruhs K. Broadcast scheduling: When fairness is fine Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 6: 421-430.  0.4
2002 Pruhs K, Wiewiora E. Evaluating the local ratio algorithm for dynamic storage allocation Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2409: 60-70.  0.375
2001 Kalyanasundaram B, Pruhs KR. Eliminating Migration in Multi-processor Scheduling Journal of Algorithms. 38: 2-24. DOI: 10.1006/jagm.2000.1128  0.352
2000 Kalyanasundaram B, Pruhs K. Speed is as powerful as clairvoyance Journal of the Acm. 47: 617-643. DOI: 10.1145/347476.347479  0.46
2000 Kalyanasundaram B, Pruhs KR, Torng E. Errata: A New Algorithm for Scheduling Periodic, Real-Time Tasks Algorithmica. 28: 269-270. DOI: 10.1007/S004530010048  0.492
2000 Kalyanasundaram B, Pruhs K. Fault-tolerant real-time scheduling Algorithmica (New York). 28: 125-144. DOI: 10.1007/S004530010034  0.38
2000 Kalyanasundaram B, Pruhs K, Velauthapillai M. Scheduling broadcasts in wireless networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1879: 290-301. DOI: 10.1002/jos.87  0.417
2000 Kalyanasundaram B, Pruhs K. Dynamic spectrum allocation: The impotency of duration notification Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1974: 421-428.  0.323
2000 Kalyanasundaram B, Pruhs KR. The online transportation problem Siam Journal On Discrete Mathematics. 13: 370-383.  0.368
1998 Pruhs K. How to design dynamic programming algorithms sans recursion Sigact News. 29: 32-35. DOI: 10.1145/281068.281075  0.36
1998 Kalyanasundaram B, Pruhs K. Maximizing job completions online Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1461: 235-246. DOI: 10.1016/S0196-6774(03)00074-9  0.434
1998 Kalyanasundaram B, Pruhs K. On-line network optimization problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1442: 268-280. DOI: 10.1007/Bfb0029573  0.459
1996 Kalyanasundaram B, Pruhs K. An optimal deterministic algorithm for online b-matching Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1180: 193-199.  0.358
1994 Bafna V, Kalyanasundaram B, Pruhs K. Not all insertion methods yield constant approximate tours in the Euclidean plane Theoretical Computer Science. 125: 345-353. DOI: 10.1016/0304-3975(94)90257-7  0.405
1993 Kalyanasundaram B, Pruhs K. A competitive analysis of algorithms for searching unknown scenes Computational Geometry: Theory and Applications. 3: 139-155. DOI: 10.1016/0925-7721(93)90032-2  0.325
1993 Kalyanasundaram B, Pruhs K. Online Weighted Matching Journal of Algorithms. 14: 478-488. DOI: 10.1006/Jagm.1993.1026  0.45
1991 Pruhs K, Manber U. The complexity of controlled selection Information and Computation. 91: 103-127. DOI: 10.1016/0890-5401(91)90076-E  0.352
Show low-probability matches.