Kirk Pruhs

According to our database1, Kirk Pruhs authored at least 193 papers between 1989 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line.
Algorithmica, 2019

2018
Tight Bounds for Double Coverage Against Weak Adversaries.
Theory Comput. Syst., 2018

The Itinerant List Update Problem.
Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

The Online Set Aggregation Problem.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017
The one-dimensional Euclidean domain: finitely many obstructions are not enough.
Social Choice and Welfare, 2017

An O(log log m)-competitive Algorithm for Online Machine Minimization.
CoRR, 2017

Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules.
Algorithmica, 2017

An O(Log Log m)-Competitive Algorithm for Online Machine Minimization.
Proceedings of the 2017 IEEE Real-Time Systems Symposium, 2017

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Speed Scaling.
Encyclopedia of Algorithms, 2016

Flow Time Minimization.
Encyclopedia of Algorithms, 2016

Competitively Scheduling Tasks with Intermediate Parallelizability.
TOPC, 2016

Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms.
Theory Comput. Syst., 2016

Weighted geometric set multi-cover via quasi-uniform sampling.
JoCG, 2016

Optimal Speed Scaling with a Solar Cell.
CoRR, 2016

Chasing Convex Bodies and Functions.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Optimal Speed Scaling with a Solar Cell - (Extended Abstract).
Proceedings of the Combinatorial Optimization and Applications, 2016

2015
The one-dimensional Euclidean domain: Finitely many obstructions are not enough.
CoRR, 2015

Tight Bounds for Double Coverage Against Weak Adversaries.
Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Stochastic Scheduling of Heavy-tailed Jobs.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Almost All Functions Require Exponential Energy.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On the Complexity of Speed Scaling.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

The power of heterogeneity in Near-Threshold Computing.
Proceedings of the Sixth International Green and Sustainable Computing Conference, 2015

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs.
Proceedings of the Approximation, 2015

2014
Online Scheduling with General Cost Functions.
SIAM J. Comput., 2014

The Geometry of Scheduling.
SIAM J. Comput., 2014

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing.
CoRR, 2014

SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors.
CoRR, 2014

A o(n) -Competitive Deterministic Algorithm for Online Matching on a Line.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing.
Proceedings of the Symposium on Theory of Computing, 2014

Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Competitively scheduling tasks with intermediate parallelizability.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Hallucination Helps: Energy Efficient Virtual Circuit Routing.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Packet Forwarding Algorithms in a Line Network.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Energy-efficient circuit design.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Complexity-theoretic obstacles to achieving energy savings with near-threshold computing.
Proceedings of the International Green Computing Conference, 2014

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Speed Scaling with an Arbitrary Power Function.
ACM Trans. Algorithms, 2013

Scheduling (Dagstuhl Seminar 13111).
Dagstuhl Reports, 2013

The Complexity of Scheduling for p-norms of Flow and Stretch
CoRR, 2013

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints.
CoRR, 2013

The Complexity of Scheduling for p-Norms of Flow and Stretch - (Extended Abstract).
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.
Theory of Computing, 2012

Scalably scheduling processes with arbitrary speedup curves.
ACM Trans. Algorithms, 2012

Speed scaling for stretch plus energy.
Oper. Res. Lett., 2012

Auction-based Admission Control for Continuous Queries in a Multi-Tenant DSMS.
IJNGC, 2012

The Power of Fair Pricing Mechanisms.
Algorithmica, 2012

Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling.
Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

Online scheduling with general cost functions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Scheduling heterogeneous processors isn't as easy as you think.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Energy Efficient Caching for Phase-Change Memory.
Proceedings of the Design and Analysis of Algorithms, 2012

Shortest-Elapsed-Time-First on a Multiprocessor.
Proceedings of the Design and Analysis of Algorithms, 2012

Multicast Routing for Energy Minimization Using Speed Scaling.
Proceedings of the Design and Analysis of Algorithms, 2012

Optimal energy trade-off schedules.
Proceedings of the 2012 International Green Computing Conference, 2012

Divorcing Made Easy.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Weighted Geometric Set Multi-cover via Quasi-uniform Sampling.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Cake cutting really is not a piece of cake.
ACM Trans. Algorithms, 2011

A tutorial on amortized local competitiveness in online scheduling.
SIGACT News, 2011

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor.
Theory Comput. Syst., 2011

Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
CoRR, 2011

Scalably Scheduling Power-Heterogeneous Processors
CoRR, 2011

Nonclairvoyant Speed Scaling for Flow and Energy.
Algorithmica, 2011

Competitive Algorithms for Due Date Scheduling.
Algorithmica, 2011

Average Rate Speed Scaling.
Algorithmica, 2011

Managing Power Heterogeneity.
Proceedings of the Theory and Practice of Algorithms in (Computer) Systems, 2011

Speed Scaling to Manage Temperature.
Proceedings of the Theory and Practice of Algorithms in (Computer) Systems, 2011

Green Computing Algorithmics.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service.
SIAM J. Comput., 2010

Open problems in real-time scheduling.
J. Scheduling, 2010

The Geometry of Scheduling
CoRR, 2010

Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability.
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Scheduling jobs with varying parallelizability to reduce variance.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

The Power of Fair Pricing Mechanisms.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Admission control mechanisms for continuous queries in the cloud.
Proceedings of the 26th International Conference on Data Engineering, 2010

Scalably Scheduling Power-Heterogeneous Processors.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Nonclairvoyantly scheduling power-heterogeneous processors.
Proceedings of the International Green Computing Conference 2010, 2010

The Geometry of Scheduling.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Scalably Scheduling Processes with Arbitrary Speedup Curves.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

10071 Executive Summary - Scheduling.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

10071 Abstracts Collection - Scheduling.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints.
Proceedings of the Algorithm Engineering, 27.06. - 02.07.2010, 2010

How to Schedule When You Have to Buy Your Energy.
Proceedings of the Approximation, 2010

2009
Speed scaling with a solar cell.
Theor. Comput. Sci., 2009

Speed Scaling for Weighted Flow Time.
SIAM J. Comput., 2009

Editorial.
J. Scheduling, 2009

Nonclairvoyant Speed Scaling for Flow and Energy
CoRR, 2009

Nonclairvoyant Speed Scaling for Flow and Energy.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Speed scaling of processes with arbitrary speedup curves on a multiprocessor.
Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Scalably scheduling processes with arbitrary speedup curves.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Speed scaling with an arbitrary power function.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Adaptive Scheduling of Web Transactions.
Proceedings of the 25th International Conference on Data Engineering, 2009

Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Speed Scaling.
Proceedings of the Encyclopedia of Algorithms, 2008

Flow Time Minimization.
Proceedings of the Encyclopedia of Algorithms, 2008

Improving the Hybrid Data Dissemination Model of Web Documents.
World Wide Web, 2008

Algorithms and metrics for processing multiple heterogeneous continuous queries.
ACM Trans. Database Syst., 2008

Getting the best response for your erg.
ACM Trans. Algorithms, 2008

Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani, Editors, Algorithmic Game Theory, Cambridge University Press (2007) ISBN 9780521872829, 776 pp.
Oper. Res. Lett., 2008

Speed Scaling of Tasks with Precedence Constraints.
Theory Comput. Syst., 2008

The Price of Stochastic Anarchy.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

The Online Transportation Problem: On the Exponential Boost of One Extra Server.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Average Rate Speed Scaling.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Scalable data dissemination using hybrid methods.
Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008

Poster session: ASETS: A self-managing transaction scheduler.
Proceedings of the 24th International Conference on Data Engineering Workshops, 2008

08071 Abstracts Collection -- Scheduling.
Proceedings of the Scheduling, 10.02. - 15.02.2008, 2008

08071 Executive Summary -- Scheduling.
Proceedings of the Scheduling, 10.02. - 15.02.2008, 2008

Confidently Cutting a Cake into Approximately Fair Pieces.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

Speed Scaling with a Solar Cell.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007
Approximation schemes for a class of subset selection problems.
Theor. Comput. Sci., 2007

Competitive online scheduling for server systems.
SIGMETRICS Performance Evaluation Review, 2007

Speed scaling to manage energy and temperature.
J. ACM, 2007

Speed scaling for weighted flow time.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Competitive Algorithms for Due Date Scheduling.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

07261 Abstracts Collection -- Fair Division.
Proceedings of the Fair Division, 24.06. - 29.06.2007, 2007

07261 Summary -- Fair Division.
Proceedings of the Fair Division, 24.06. - 29.06.2007, 2007

2006
Online weighted flow time and deadline scheduling.
J. Discrete Algorithms, 2006

Network awareness and application adaptability.
Inf. Syst. E-Business Management, 2006

Efficient Scheduling of Heterogeneous Continuous Queries.
Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Cake cutting really is not a piece of cake.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Decomposing Data-Centric Storage Query Hot-Spots in Sensor Networks.
Proceedings of the 3rd Annual International ICST Conference on Mobile and Ubiquitous Systems: Computing, 2006

To Broadcast Push or Not and What?.
Proceedings of the 7th International Conference on Mobile Data Management (MDM 2006), 2006

Balanced Allocations of Cake.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Secure-CITI Critical Information-Technology Infrastructure.
Proceedings of the 7th Annual International Conference on Digital Government Research, 2006

KDDCS: a load-balanced in-network data-centric storage scheme for sensor networks.
Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management, 2006

2005
A maiden analysis of longest wait first.
ACM Trans. Algorithms, 2005

Algorithmic problems in power management.
SIGACT News, 2005

Fault-Tolerant Scheduling.
SIAM J. Comput., 2005

A Comparison of Multicast Pull Models.
Algorithmica, 2005

Freshness-Aware Scheduling of Continuous Queries in the Dynamic Web.
Proceedings of the Eight International Workshop on the Web & Databases (WebDB 2005), 2005

Speed Scaling of Tasks with Precedence Constraints.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Speed Scaling to Manage Temperature.
Proceedings of the STACS 2005, 2005

Zone sharing: a hot-spots decomposition scheme for data-centric storage in sensor networks.
Proceedings of the 2nd Workshop on Data Management for Sensor Networks, 2005

2004
Online Scheduling.
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

Semi-clairvoyant scheduling.
Theor. Comput. Sci., 2004

Scalable Dissemination: What's Hot and What's Not.
Proceedings of the Seventh International Workshop on the Web and Databases, 2004

Getting the Best Response for Your Erg.
Proceedings of the Algorithm Theory, 2004

A maiden analysis of Longest Wait First.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Approximation Schemes for a Class of Subset Selection Problems.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

A Constant Approximation Algorithm for Sorting Buffers.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Server Scheduling in the Weighted lp Norm.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Dynamic Speed Scaling to Manage Energy and Temperature.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Editorial: Special Issue on On-Line Scheduling.
J. Scheduling, 2003

Editorial: Special Issue on On-line Scheduling.
J. Scheduling, 2003

Dedication.
J. Scheduling, 2003

Foreword.
J. Algorithms, 2003

Maximizing job completions online.
J. Algorithms, 2003

Minimizing flow time nonclairvoyantly.
J. ACM, 2003

Multicast Pull Scheduling: When Fairness Is Fine.
Algorithmica, 2003

Middleware Support for Multicast-based Data Dissemination: A Working Reality.
Proceedings of the 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS 2003), 2003

Server scheduling in the Lp norm: a rising tide lifts all boat.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

An Optimized Multicast-based Data Dissemination Middleware.
Proceedings of the 19th International Conference on Data Engineering, 2003

Semi-clairvoyant Scheduling.
Proceedings of the Algorithms, 2003

2002
Caching for Web Searching.
Algorithmica, 2002

Broadcast scheduling: when fairness is fine.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

A Comparison of Multicast Pull Models.
Proceedings of the Algorithms, 2002

Evaluating the Local Ratio Algorithm for Dynamic Storage Allocation.
Proceedings of the Algorithm Engineering and Experiments, 4th International Workshop, 2002

2001
Eliminating Migration in Multi-processor Scheduling.
J. Algorithms, 2001

Better client OFF time prediction to improve performance in web information systems.
Proceedings of the 3rd International Workshop on Web Information and Data Management (WIDM 2001), 2001

Online Weighted Flow Time and Deadline Scheduling.
Proceedings of the Approximation, 2001

2000
An optimal deterministic algorithm for online b-matching.
Theor. Comput. Sci., 2000

The Online Transportation Problem.
SIAM J. Discrete Math., 2000

Speed is as powerful as clairvoyance.
J. ACM, 2000

Errata: A New Algorithm for Scheduling Periodic, Real-Time Tasks.
Algorithmica, 2000

Fault-Tolerant Real-Time Scheduling.
Algorithmica, 2000

Caching for Web Searching.
Proceedings of the Algorithm Theory, 2000

Dynamic Spectrum Allocation: The Impotency of Duration Notification.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

Scheduling Broadcasts in Wireless Networks.
Proceedings of the Algorithms, 2000

1999
Eliminating Migration in Multi-Processor Scheduling.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
How to design dynamic programming algorithms sans recursion.
SIGACT News, 1998

Maximizing Job Completions Online.
Proceedings of the Algorithms, 1998

1997
On-Line Load Balancing of Temporary Tasks.
J. Algorithms, 1997

Minimizing Flow Time Nonclairvoyantly.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Fault-Tolerant Real-Time Scheduling.
Proceedings of the Algorithms, 1997

1996
An Optimal Deterministic Algorithm for Online b-Matching.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

On-line Network Optimization Problems.
Proceedings of the Online Algorithms, 1996

1995
Using Local Adaptations to Reconfigure a Spanning Tree of a Network.
Discrete Applied Mathematics, 1995

Speed is as Powerful as Clairvoyance.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

The Online Transportation Problem.
Proceedings of the Algorithms, 1995

1994
Constructing Competitive Tours from Local Information.
Theor. Comput. Sci., 1994

Not All Insertion Methods Yield Constant Approximate Tours in the Euclidean Plane.
Theor. Comput. Sci., 1994

Average-Case Scalable On-Line Algorithms for Fault Replacement.
Inf. Process. Lett., 1994

Fault-tolerant scheduling.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993
Online Weighted Matching.
J. Algorithms, 1993

A Competitive Analysis of Algorithms for Searching Unknown Scenes.
Comput. Geom., 1993

Online Load Balancing of Temporary Tasks.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Constructing Competitive Tours From Local Information.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

1992
A Competitive Analysis of Nearest Neighbor Based Algorithms for Searching Unknown Scenes (Preliminary Version).
Proceedings of the STACS 92, 1992

1991
The Complexity of Controlled Selection
Inf. Comput., March, 1991

On-Line Weighted Matching.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Visual Searching and Mapping.
Proceedings of the On-Line Algorithms, 1991

Online Weighted Matching.
Proceedings of the On-Line Algorithms, 1991

1989
The Complexity of Controlled Selection.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989


  Loading...