Kirk Pruhs

ORCID

Publication Activity (10 Years)

Years Active: 1989-2024
Publications (10 Years): 57

Top Venues

Publications

Benjamin Moseley, Kirk Pruhs, Clifford Stein, Rudy Zhou
A competitive algorithm for throughput maximization on identical machines. Math. Program. 206 (1) (2024)
Kunal Agrawal, Benjamin Moseley, Heather Newman, Kirk Pruhs
Scheduling Out-Trees Online to Optimize Maximum Flow. SPAA (2024)
Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs
On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings. ICDT (2024)
Benjamin Moseley, Heather Newman, Kirk Pruhs
The Public University Secretary Problem. SOSA (2024)
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Clifford Stein
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing. SIAM J. Comput. 53 (3) (2024)
Stephen Arndt, Josh Ascher, Kirk Pruhs
An $O(\log n)$-Competitive Posted-Price Algorithm for Online Matching on the Line. CoRR (2023)
Benjamin Moseley, Heather Newman, Kirk Pruhs
Online k-Median with Consistent Clusters. CoRR (2023)
Stephen Arndt, Josh Ascher, Kirk Pruhs
Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem. CoRR (2023)
Bala Kalyanasundaram, Kirk Pruhs, Clifford Stein
A randomized algorithm for online metric b-matching. Oper. Res. Lett. 51 (6) (2023)
Stephen Arndt, Josh Ascher, Kirk Pruhs
An O(log n)-Competitive Posted-Price Algorithm for Online Matching on the Line. COCOA (1) (2023)
Stephen Arndt, Josh Ascher, Kirk Pruhs
Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem. LAGOS (2023)
Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs
Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs. CoRR (2023)
Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs
On the Convergence Rate of Linear Datalogo over Stable Semirings. CoRR (2023)
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
On the impossibility of decomposing binary matroids. Oper. Res. Lett. 50 (5) (2022)
Benjamin Moseley, Kirk Pruhs, Clifford Stein, Rudy Zhou
A Competitive Algorithm for Throughput Maximization on Identical Machines. IPCO (2022)
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
On the Impossibility of Decomposing Binary Matroids. CoRR (2022)
Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, Alireza Samadian
Optimizing Polymatroid Functions. CoRR (2022)
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
An Efficient Reduction of a Gammoid to a Partition Matroid. ESA (2021)
Mahmoud Abo Khamis, Ryan R. Curtin, Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, Alireza Samadian
An Approximation Algorithm for the Matrix Tree Multiplication Problem. MFCS (2021)
Benjamin Moseley, Kirk Pruhs, Clifford Stein, Rudy Zhou
A Competitive Algorithm for Throughout Maximization on Identical Machines. CoRR (2021)
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
An Efficient Reduction of a Gammoid to a Partition Matroid. CoRR (2021)
Max Bender, Jacob Gilbert, Kirk Pruhs
A Poly-log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider. FCT (2021)
Sungjin Im, Benjamin Moseley, Kirk Pruhs
The matroid intersection cover problem. Oper. Res. Lett. 49 (1) (2021)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
Approximate Aggregate Queries Under Additive Inequalities. APOCS (2021)
Benjamin Moseley, Kirk Pruhs, Alireza Samadian, Yuyan Wang
Relational Algorithms for k-Means Clustering. ICALP (2021)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
A Relational Gradient Descent Algorithm For Support Vector Machine Training. APOCS (2021)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
Instance Optimal Join Size Estimation. LAGOS (2021)
Sonia Cromp, Alireza Samadian, Kirk Pruhs
Relational Boosted Regression Trees. CoRR (2021)
Max Bender, Jacob Gilbert, Aditya Krishnan, Kirk Pruhs
Competitively Pricing Parking in a Tree. CoRR (2020)
Benjamin Moseley, Kirk Pruhs, Alireza Samadian, Yuyan Wang
Relational Algorithms for k-means Clustering. CoRR (2020)
Sungjin Im, Benjamin Moseley, Kamesh Munagala, Kirk Pruhs
Dynamic Weighted Fairness with Minimal Disruptions. CoRR (2020)
Sungjin Im, Benjamin Moseley, Kamesh Munagala, Kirk Pruhs
Dynamic Weighted Fairness with Minimal Disruptions. SIGMETRICS (Abstracts) (2020)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
A Relational Gradient Descent Algorithm For Support Vector Machine Training. CoRR (2020)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
Approximate Aggregate Queries Under Additive Inequalities. CoRR (2020)
Sungjin Im, Benjamin Moseley, Kamesh Munagala, Kirk Pruhs
Dynamic Weighted Fairness with Minimal Disruptions. Proc. ACM Meas. Anal. Comput. Syst. 4 (1) (2020)
Max Bender, Jacob Gilbert, Aditya Krishnan, Kirk Pruhs
Competitively Pricing Parking in a Tree. WINE (2020)
Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
Instance Optimal Join Size Estimation. CoRR (2020)
Alireza Samadian, Kirk Pruhs, Benjamin Moseley, Sungjin Im, Ryan R. Curtin
Unconditional Coresets for Regularized Loss Minimization. AISTATS (2020)
Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Clifford Stein
Hallucination Helps: Energy Efficient Virtual Circuit Routing. SIAM J. Comput. 49 (1) (2020)
Ryan R. Curtin, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
On Coresets for Regularized Loss Minimization. CoRR (2019)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Manish Purohit
Matroid Coflow Scheduling. ICALP (2019)
Zhengguo Chen, Quan Deng, Nong Xiao, Kirk Pruhs, Youtao Zhang
DWMAcc: Accelerating Shift-based CNNs with Domain Wall Memories. ACM Trans. Embed. Comput. Syst. 18 (5s) (2019)
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line. Algorithmica 81 (7) (2019)
Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, José Verschae
The Online Set Aggregation Problem. LATIN (2018)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
Tight Bounds for Double Coverage Against Weak Adversaries. Theory Comput. Syst. 62 (2) (2018)
Neil Olver, Kirk Pruhs, Kevin Schewior, René Sitters, Leen Stougie
The Itinerant List Update Problem. WAOA (2018)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Clifford Stein
Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing. ESA (2017)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Clifford Stein
An O(Log Log m)-Competitive Algorithm for Online Machine Minimization. RTSS (2017)
Antonios Antoniadis, Neal Barcelo, Mario E. Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules. Algorithmica 79 (2) (2017)
Jiehua Chen, Kirk Pruhs, Gerhard J. Woeginger
The one-dimensional Euclidean domain: finitely many obstructions are not enough. Soc. Choice Welf. 48 (2) (2017)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Clifford Stein
An O(log log m)-competitive Algorithm for Online Machine Minimization. CoRR (2017)
Nikhil Bansal, Kirk Pruhs
Weighted geometric set multi-cover via quasi-uniform sampling. J. Comput. Geom. 7 (1) (2016)
Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs
Optimal Speed Scaling with a Solar Cell. CoRR (2016)
Christos Kaklamanis, Kirk Pruhs
Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms. Theory Comput. Syst. 58 (1) (2016)
Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs
Optimal Speed Scaling with a Solar Cell - (Extended Abstract). COCOA (2016)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Eric Torng
Competitively Scheduling Tasks with Intermediate Parallelizability. ACM Trans. Parallel Comput. 3 (1) (2016)
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, Michele Scquizzato
Chasing Convex Bodies and Functions. LATIN (2016)
Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
On the Complexity of Speed Scaling. MFCS (2) (2015)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
Tight Bounds for Double Coverage Against Weak Adversaries. WAOA (2015)
Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. APPROX-RANDOM (2015)
Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
The power of heterogeneity in Near-Threshold Computing. IGSC (2015)
Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Almost All Functions Require Exponential Energy. MFCS (2) (2015)
Sungjin Im, Benjamin Moseley, Kirk Pruhs
Stochastic Scheduling of Heavy-tailed Jobs. STACS (2015)
Jiehua Chen, Kirk Pruhs, Gerhard J. Woeginger
The one-dimensional Euclidean domain: Finitely many obstructions are not enough. CoRR (2015)
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing. CoRR (2014)
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, Kirk Pruhs
SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. CoRR (2014)
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Complexity-theoretic obstacles to achieving energy savings with near-threshold computing. IGCC (2014)
Nikhil Bansal, Kirk Pruhs
The Geometry of Scheduling. SIAM J. Comput. 43 (5) (2014)
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
A o(n) -Competitive Deterministic Algorithm for Online Matching on a Line. WAOA (2014)
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, Kirk Pruhs
SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. FOCS (2014)
Antonios Antoniadis, Neal Barcelo, Daniel Cole, Kyle Fox, Benjamin Moseley, Michael Nugent, Kirk Pruhs
Packet Forwarding Algorithms in a Line Network. LATIN (2014)
Antonios Antoniadis, Neal Barcelo, Mario E. Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. STACS (2014)
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing. STOC (2014)
Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Hallucination Helps: Energy Efficient Virtual Circuit Routing. SODA (2014)
Sungjin Im, Benjamin Moseley, Kirk Pruhs
Online Scheduling with General Cost Functions. SIAM J. Comput. 43 (1) (2014)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Eric Torng
Competitively scheduling tasks with intermediate parallelizability. SPAA (2014)
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Energy-efficient circuit design. ITCS (2014)
Susanne Albers, Onno J. Boxma, Kirk Pruhs
Scheduling (Dagstuhl Seminar 13111). Dagstuhl Reports 3 (3) (2013)
Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
Speed Scaling with an Arbitrary Power Function. ACM Trans. Algorithms 9 (2) (2013)
Benjamin Moseley, Kirk Pruhs, Cliff Stein
The Complexity of Scheduling for p-Norms of Flow and Stretch - (Extended Abstract). IPCO (2013)
Benjamin Moseley, Kirk Pruhs, Cliff Stein
The Complexity of Scheduling for p-norms of Flow and Stretch CoRR (2013)
Neal Barcelo, Daniel Cole, Dimitrios Letsios, Michael Nugent, Kirk Pruhs
Optimal energy trade-off schedules. Sustain. Comput. Informatics Syst. 3 (3) (2013)
Ahmed Abousamra, David P. Bunde, Kirk Pruhs
An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints. CoRR (2013)
Neal Barcelo, Miao Zhou, Daniel Cole, Michael Nugent, Kirk Pruhs
Energy Efficient Caching for Phase-Change Memory. MedAlg (2012)
Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, Kirk Pruhs
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. Theory Comput. 8 (1) (2012)
Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs
Scheduling heterogeneous processors isn't as easy as you think. SODA (2012)
Sungjin Im, Benjamin Moseley, Kirk Pruhs
Online scheduling with general cost functions. SODA (2012)
Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth
The Power of Fair Pricing Mechanisms. Algorithmica 63 (3) (2012)
Lory Al Moakar, Panos K. Chrysanthis, Christine Chung, Shenoda Guirguis, Alexandros Labrinidis, Panayiotis Neophytou, Kirk Pruhs
Auction-based Admission Control for Continuous Queries in a Multi-Tenant DSMS. Int. J. Next Gener. Comput. 3 (3) (2012)
Neal Barcelo, Sungjin Im, Benjamin Moseley, Kirk Pruhs
Shortest-Elapsed-Time-First on a Multiprocessor. MedAlg (2012)
Jeff Edmonds, Kirk Pruhs
Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms 8 (3) (2012)
Kirk Pruhs, Gerhard J. Woeginger
Divorcing Made Easy. FUN (2012)
Daniel Cole, Dimitrios Letsios, Michael Nugent, Kirk Pruhs
Optimal energy trade-off schedules. IGCC (2012)
Daniel Cole, Sungjin Im, Benjamin Moseley, Kirk Pruhs
Speed scaling for stretch plus energy. Oper. Res. Lett. 40 (3) (2012)
Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs
Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling. WAOA (2012)
Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Multicast Routing for Energy Minimization Using Speed Scaling. MedAlg (2012)
Nikhil Bansal, Kirk Pruhs
Weighted Geometric Set Multi-cover via Quasi-uniform Sampling. ESA (2012)
Sungjin Im, Benjamin Moseley, Kirk Pruhs
A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42 (2) (2011)
Ho-Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs
Nonclairvoyant Speed Scaling for Flow and Energy. Algorithmica 61 (3) (2011)
Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs
Average Rate Speed Scaling. Algorithmica 60 (4) (2011)

Kirk Pruhs.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Kirk Pruhs