Kirk Pruhs
From MaRDI portal
List of research outcomes
This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!
| Publication | Date of Publication | Type |
|---|---|---|
| An \(O(\log n)\)-competitive posted-price algorithm for online matching on the line j=' ' a=' ' j#=6 a#=6 | 2024-09-16 | Paper |
| A competitive algorithm for throughput maximization on identical machines Mathematical Programming. Series A. Series B j='Mathematical Programming. Series A. Series B' a=' ' j#=44 a#=6 | 2024-08-20 | Paper |
| An optimal deterministic algorithm for online b-matching j=' ' a=' ' j#=6 a#=6 | 2024-07-05 | Paper |
| A randomized algorithm for online metric b-matching Operations Research Letters j='Operations Research Letters' a=' ' j#=27 a#=6 | 2024-06-17 | Paper |
| Cluster before you hallucinate: node-capacitated network design and energy efficient routing SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2024-06-05 | Paper |
| The public university secretary problem j=' ' a=' ' j#=6 a#=6 | 2024-05-29 | Paper |
| scientific article; zbMATH DE number 7740917 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2023-09-20 | Paper |
| An approximation algorithm for the matrix tree multiplication problem j=' ' a=' ' j#=6 a#=6 | 2023-08-08 | Paper |
| The online transportation problem Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2023-05-08 | Paper |
| Competitively pricing parking in a tree j=' ' a=' ' j#=6 a#=6 | 2023-03-21 | Paper |
| Online load balancing of temporary tasks Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2023-01-18 | Paper |
| On the impossibility of decomposing binary matroids Operations Research Letters j='Operations Research Letters' a=' ' j#=27 a#=6 | 2022-10-17 | Paper |
| A competitive analysis of nearest neighbor based algorithms for searching unknown scenes STACS 92 j='STACS 92' a=' ' j#=8 a#=6 | 2022-08-18 | Paper |
| A competitive algorithm for throughput maximization on identical machines j=' ' a=' ' j#=6 a#=6 | 2022-08-16 | Paper |
| Matroid coflow scheduling j=' ' a=' ' j#=6 a#=6 | 2022-07-21 | Paper |
| On the Impossibility of Decomposing Binary Matroids j=' ' a='2206.12896' j#=6 a#=10 | 2022-06-26 | Paper |
| A poly-log competitive posted-price algorithm for online metrical matching on a spider j=' ' a=' ' j#=6 a#=6 | 2022-05-20 | Paper |
| Fault-tolerant real-time scheduling Algorithms — ESA '97 j='Algorithms — ESA '97' a=' ' j#=22 a#=6 | 2021-12-20 | Paper |
| The matroid intersection cover problem Operations Research Letters j='Operations Research Letters' a=' ' j#=27 a#=6 | 2021-04-07 | Paper |
| Minimizing maximum flow time on related machines via dynamic posted pricing j=' ' a=' ' j#=6 a#=6 | 2020-05-27 | Paper |
| The online set aggregation problem j=' ' a=' ' j#=6 a#=6 | 2020-02-12 | Paper |
| Hallucination helps: energy efficient virtual circuit routing SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2020-01-21 | Paper |
| Hallucination helps: energy efficient virtual circuit routing Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms j='Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms' a=' ' j#=80 a#=6 | 2019-06-20 | Paper |
| A \(o(n)\)-competitive deterministic algorithm for online matching on a line Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2019-05-21 | Paper |
| Online scheduling with general cost functions j=' ' a=' ' j#=6 a#=6 | 2019-05-10 | Paper |
| Scheduling heterogeneous processors isn't as easy as you think j=' ' a=' ' j#=6 a#=6 | 2019-05-10 | Paper |
| Speed scaling with an arbitrary power function j=' ' a=' ' j#=6 a#=6 | 2019-05-06 | Paper |
| scientific article; zbMATH DE number 7051237 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2019-05-06 | Paper |
| Constructing competitive tours from local information Automata, Languages and Programming j='Automata, Languages and Programming' a=' ' j#=35 a#=6 | 2019-03-29 | Paper |
| The itinerant list update problem j=' ' a=' ' j#=6 a#=6 | 2019-01-15 | Paper |
| Getting the best response for your erg ACM Transactions on Algorithms j='ACM Transactions on Algorithms' a=' ' j#=30 a#=6 | 2018-11-05 | Paper |
| Tight bounds for double coverage against weak adversaries Theory of Computing Systems j='Theory of Computing Systems' a=' ' j#=27 a#=6 | 2018-04-12 | Paper |
| Efficient computation of optimal energy and fractional weighted flow trade-off schedules Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2017-10-10 | Paper |
| A 2-competitive algorithm for online convex optimization with switching costs j=' ' a=' ' j#=6 a#=6 | 2017-08-31 | Paper |
| The one-dimensional Euclidean domain: finitely many obstructions are not enough Social Choice and Welfare j='Social Choice and Welfare' a=' ' j#=25 a#=6 | 2017-05-23 | Paper |
| Energy-efficient circuit design Proceedings of the 5th conference on Innovations in theoretical computer science j='Proceedings of the 5th conference on Innovations in theoretical computer science' a=' ' j#=80 a#=6 | 2017-05-19 | Paper |
| Weighted geometric set multi-cover via quasi-uniform sampling j=' ' a=' ' j#=6 a#=6 | 2017-03-30 | Paper |
| Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules j=' ' a=' ' j#=6 a#=6 | 2017-03-03 | Paper |
| Optimal speed scaling with a solar cell (extended abstract) Combinatorial Optimization and Applications j='Combinatorial Optimization and Applications' a=' ' j#=43 a#=6 | 2017-02-01 | Paper |
| scientific article; zbMATH DE number 6677416 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2017-01-24 | Paper |
| Fault-tolerant scheduling (extended abstract) Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 j='Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94' a=' ' j#=87 a#=6 | 2016-09-01 | Paper |
| Chasing convex bodies and functions LATIN 2016: Theoretical Informatics j='LATIN 2016: Theoretical Informatics' a=' ' j#=35 a#=6 | 2016-05-03 | Paper |
| Tight Bounds for Double Coverage Against Weak Adversaries Approximation and Online Algorithms j='Approximation and Online Algorithms' a=' ' j#=35 a#=6 | 2016-02-26 | Paper |
| A \(o(n)\)-competitive deterministic algorithm for online matching on a line Approximation and Online Algorithms j='Approximation and Online Algorithms' a=' ' j#=35 a#=6 | 2015-11-20 | Paper |
| Minimizing flow time nonclairvoyantly Journal of the ACM j='Journal of the ACM' a=' ' j#=18 a#=6 | 2015-11-12 | Paper |
| Almost all functions require exponential energy Mathematical Foundations of Computer Science 2015 j='Mathematical Foundations of Computer Science 2015' a=' ' j#=49 a#=6 | 2015-09-16 | Paper |
| On the complexity of speed scaling Mathematical Foundations of Computer Science 2015 j='Mathematical Foundations of Computer Science 2015' a=' ' j#=49 a#=6 | 2015-09-16 | Paper |
| A maiden analysis of longest wait first ACM Transactions on Algorithms j='ACM Transactions on Algorithms' a=' ' j#=30 a#=6 | 2015-09-02 | Paper |
| A maiden analysis of longest wait first j=' ' a=' ' j#=6 a#=6 | 2015-08-03 | Paper |
| Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing Proceedings of the forty-sixth annual ACM symposium on Theory of computing j='Proceedings of the forty-sixth annual ACM symposium on Theory of computing' a=' ' j#=74 a#=6 | 2015-06-26 | Paper |
| The geometry of scheduling SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2015-02-09 | Paper |
| Speed scaling for weighted flow time j=' ' a=' ' j#=6 a#=6 | 2014-12-18 | Paper |
| Speed scaling with an arbitrary power function ACM Transactions on Algorithms j='ACM Transactions on Algorithms' a=' ' j#=30 a#=6 | 2014-12-05 | Paper |
| Scalably scheduling processes with arbitrary speedup curves ACM Transactions on Algorithms j='ACM Transactions on Algorithms' a=' ' j#=30 a#=6 | 2014-09-09 | Paper |
| Cake cutting really is not a piece of cake ACM Transactions on Algorithms j='ACM Transactions on Algorithms' a=' ' j#=30 a#=6 | 2014-09-09 | Paper |
| Online scheduling with general cost functions SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2014-06-04 | Paper |
| Online primal-dual for non-linear optimization with applications to speed scaling Approximation and Online Algorithms j='Approximation and Online Algorithms' a=' ' j#=35 a#=6 | 2013-09-13 | Paper |
| Multicast routing for energy minimization using speed scaling Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2013-04-19 | Paper |
| Shortest-elapsed-time-first on a multiprocessor Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2013-04-19 | Paper |
| The Complexity of Scheduling for p-Norms of Flow and Stretch Integer Programming and Combinatorial Optimization j='Integer Programming and Combinatorial Optimization' a=' ' j#=50 a#=6 | 2013-03-19 | Paper |
| Speed scaling of processes with arbitrary speedup curves on a multiprocessor Theory of Computing Systems j='Theory of Computing Systems' a=' ' j#=27 a#=6 | 2012-12-10 | Paper |
| Improved bounds for speed scaling in devices obeying the cube-root rule Theory of Computing j='Theory of Computing' a=' ' j#=19 a#=6 | 2012-09-27 | Paper |
| Weighted geometric set multi-cover via quasi-uniform sampling Algorithms – ESA 2012 j='Algorithms – ESA 2012' a=' ' j#=23 a#=6 | 2012-09-25 | Paper |
| Speed scaling for stretch plus energy Operations Research Letters j='Operations Research Letters' a=' ' j#=27 a#=6 | 2012-08-17 | Paper |
| The power of fair pricing mechanisms Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2012-04-26 | Paper |
| Nonclairvoyant speed scaling for flow and energy j=' ' a=' ' j#=6 a#=6 | 2012-04-24 | Paper |
| Nonclairvoyant speed scaling for flow and energy Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2011-11-07 | Paper |
| Average rate speed scaling Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2011-07-01 | Paper |
| Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2011-04-04 | Paper |
| Open problems in real-time scheduling Journal of Scheduling j='Journal of Scheduling' a=' ' j#=21 a#=6 | 2011-04-01 | Paper |
| Competitive algorithms for due date scheduling Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2011-03-30 | Paper |
| Minimizing maximum flowtime of jobs with arbitrary parallelizability Approximation and Online Algorithms j='Approximation and Online Algorithms' a=' ' j#=35 a#=6 | 2011-02-15 | Paper |
| How to schedule when you have to buy your energy Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques j='Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques' a=' ' j#=87 a#=6 | 2010-09-10 | Paper |
| Scalably Scheduling Power-Heterogeneous Processors Automata, Languages and Programming j='Automata, Languages and Programming' a=' ' j#=35 a#=6 | 2010-09-07 | Paper |
| Speed scaling for weighted flow time SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2010-09-06 | Paper |
| Cake cutting really is not a piece of cake Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 j='Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06' a=' ' j#=90 a#=6 | 2010-08-16 | Paper |
| Server scheduling in the L p norm Proceedings of the thirty-fifth annual ACM symposium on Theory of computing j='Proceedings of the thirty-fifth annual ACM symposium on Theory of computing' a=' ' j#=75 a#=6 | 2010-08-16 | Paper |
| The power of fair pricing mechanisms LATIN 2010: Theoretical Informatics j='LATIN 2010: Theoretical Informatics' a=' ' j#=35 a#=6 | 2010-04-27 | Paper |
| Semi-clairvoyant scheduling Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2010-03-03 | Paper |
| Speed scaling with a solar cell Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 2009-11-04 | Paper |
| LATIN 2004: Theoretical Informatics Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2009-05-07 | Paper |
| LATIN 2004: Theoretical Informatics Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2009-05-07 | Paper |
| LATIN 2004: Theoretical Informatics Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2009-05-07 | Paper |
| Speed scaling to manage energy and temperature Journal of the ACM j='Journal of the ACM' a=' ' j#=18 a#=6 | 2008-12-21 | Paper |
| Confidently Cutting a Cake into Approximately Fair Pieces Algorithmic Aspects in Information and Management j='Algorithmic Aspects in Information and Management' a=' ' j#=49 a#=6 | 2008-07-10 | Paper |
| Speed Scaling with a Solar Cell Algorithmic Aspects in Information and Management j='Algorithmic Aspects in Information and Management' a=' ' j#=49 a#=6 | 2008-07-10 | Paper |
| Speed scaling of tasks with precedence constraints Theory of Computing Systems j='Theory of Computing Systems' a=' ' j#=27 a#=6 | 2008-06-06 | Paper |
| The Price of Stochastic Anarchy Algorithmic Game Theory j='Algorithmic Game Theory' a=' ' j#=23 a#=6 | 2008-05-02 | Paper |
| The Online Transportation Problem: On the Exponential Boost of One Extra Server Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2008-04-15 | Paper |
| Average Rate Speed Scaling Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2008-04-15 | Paper |
| Dedicationcategory:Dedication Journal of Scheduling j='Journal of Scheduling' a=' ' j#=21 a#=6 | 2007-12-20 | Paper |
| Competitive Algorithms for Due Date Scheduling Automata, Languages and Programming j='Automata, Languages and Programming' a=' ' j#=35 a#=6 | 2007-11-28 | Paper |
| Approximation schemes for a class of subset selection problems Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 2007-09-18 | Paper |
| Approximation and Online Algorithms Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2007-02-12 | Paper |
| Online weighted flow time and deadline scheduling Journal of Discrete Algorithms j='Journal of Discrete Algorithms' a=' ' j#=30 a#=6 | 2006-10-31 | Paper |
| A comparison of multicast pull models Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2006-03-21 | Paper |
| STACS 2005 Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2005-12-02 | Paper |
| Fault-Tolerant Scheduling SIAM Journal on Computing j='SIAM Journal on Computing' a=' ' j#=25 a#=6 | 2005-09-16 | Paper |
| Algorithm Theory - SWAT 2004 Lecture Notes in Computer Science j='Lecture Notes in Computer Science' a=' ' j#=33 a#=6 | 2005-09-07 | Paper |
| scientific article; zbMATH DE number 2119692 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2004-11-29 | Paper |
| Semi-clairvoyant scheduling Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 2004-11-23 | Paper |
| Maximizing job completions online Journal of Algorithms j='Journal of Algorithms' a=' ' j#=21 a#=6 | 2004-10-01 | Paper |
| scientific article; zbMATH DE number 2080221 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2004-08-04 | Paper |
| Multicast pull scheduling: When fairness is fine Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2003-08-17 | Paper |
| Dynamic spectrum allocation: the impotency of duration notification. Journal of Scheduling j='Journal of Scheduling' a=' ' j#=21 a#=6 | 2003-07-27 | Paper |
| scientific article; zbMATH DE number 1947442 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2003-07-08 | Paper |
| Speed is as powerful as clairvoyance Journal of the ACM j='Journal of the ACM' a=' ' j#=18 a#=6 | 2003-06-25 | Paper |
| scientific article; zbMATH DE number 1926660 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2003-06-11 | Paper |
| scientific article; zbMATH DE number 1833400 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2002-11-21 | Paper |
| Caching for web searching Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2002-06-17 | Paper |
| Scheduling broadcasts in wireless networks Journal of Scheduling j='Journal of Scheduling' a=' ' j#=21 a#=6 | 2002-05-14 | Paper |
| scientific article; zbMATH DE number 1670667 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2001-12-18 | Paper |
| Eliminating migration in multi-processor scheduling Journal of Algorithms j='Journal of Algorithms' a=' ' j#=21 a#=6 | 2001-10-07 | Paper |
| scientific article; zbMATH DE number 1617255 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2001-07-11 | Paper |
| Errata: A new algorithm for scheduling periodic, real-time tasks Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2000-12-03 | Paper |
| Fault-tolerant real-time scheduling Algorithmica j='Algorithmica' a=' ' j#=12 a#=6 | 2000-08-27 | Paper |
| An optimal deterministic algorithm for online \(b\)-matching Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 2000-08-23 | Paper |
| The Online Transportation Problem SIAM Journal on Discrete Mathematics j='SIAM Journal on Discrete Mathematics' a=' ' j#=36 a#=6 | 2000-07-20 | Paper |
| Constructing competitive tours from local information Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 2000-06-21 | Paper |
| scientific article; zbMATH DE number 1306855 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 2000-04-26 | Paper |
| scientific article; zbMATH DE number 1305442 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 1999-06-17 | Paper |
| On-Line Load Balancing of Temporary Tasks Journal of Algorithms j='Journal of Algorithms' a=' ' j#=21 a#=6 | 1997-03-18 | Paper |
| Using local adaptations to reconfigure a spanning tree of a network Discrete Applied Mathematics j='Discrete Applied Mathematics' a=' ' j#=28 a#=6 | 1995-06-11 | Paper |
| Average-case scalable on-line algorithms for fault replacement Information Processing Letters j='Information Processing Letters' a=' ' j#=30 a#=6 | 1994-11-20 | Paper |
| Not all insertion methods yield constant approximate tours in the Euclidean plane Theoretical Computer Science j='Theoretical Computer Science' a=' ' j#=28 a#=6 | 1994-04-05 | Paper |
| A competitive analysis of algorithms for searching unknown scenes Computational Geometry j='Computational Geometry' a=' ' j#=22 a#=6 | 1993-10-24 | Paper |
| scientific article; zbMATH DE number 432824 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 1993-10-20 | Paper |
| Online Weighted Matching Journal of Algorithms j='Journal of Algorithms' a=' ' j#=21 a#=6 | 1993-06-29 | Paper |
| scientific article; zbMATH DE number 65700 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 1992-09-27 | Paper |
| scientific article; zbMATH DE number 65705 (Why is no real title available?) j=' ' a=' ' j#=6 a#=6 | 1992-09-27 | Paper |
| The complexity of controlled selection Information and Computation j='Information and Computation' a=' ' j#=27 a#=6 | 1992-06-25 | Paper |
Research outcomes over time
This page was built for person: Kirk Pruhs
