Kirk Pruhs

MFCS Conference 2021 Conference Paper

An Approximation Algorithm for the Matrix Tree Multiplication Problem

• Mahmoud Abo Khamis
• Ryan R. Curtin
• Sungjin Im
• Benjamin Moseley
• Hung Q. Ngo 0001
• Kirk Pruhs
• Alireza Samadian

We consider the Matrix Tree Multiplication problem. This problem is a generalization of the classic Matrix Chain Multiplication problem covered in the dynamic programming chapter of many introductory algorithms textbooks. An instance of the Matrix Tree Multiplication problem consists of a rooted tree with a matrix associated with each edge. The output is, for each leaf in the tree, the product of the matrices on the chain/path from the root to that leaf. Matrix multiplications that are shared between various chains need only be computed once, potentially being shared between different root to leaf chains. Algorithms are evaluated by the number of scalar multiplications performed. Our main result is a linear time algorithm for which the number of scalar multiplications performed is at most 15 times the optimal number of scalar multiplications.

STOC Conference 2014 Conference Paper

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

• Ravishankar Krishnaswamy
• Viswanath Nagarajan
• Kirk Pruhs
• Cliff Stein 0001

We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O (log 3 n )- approximate with O (log 4 n ) congestion. This translates back to a O (log 4α+3 n )-approximation for the multicast energy-minimization routing problem, where α is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O (log 5 n )-approximate with O (log 12 n ) congestion, which translates back to a O (log 12α+5 n )-approximation for the unicast energy-minimization routing problem.

SODA Conference 2014 Conference Paper

Hallucination Helps: Energy Efficient Virtual Circuit Routing

• Antonios Antoniadis 0001
• Sungjin Im
• Ravishankar Krishnaswamy
• Benjamin Moseley
• Viswanath Nagarajan
• Kirk Pruhs
• Cliff Stein 0001

FOCS Conference 2014 Conference Paper

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors

• Sungjin Im
• Janardhan Kulkarni
• Kamesh Munagala
• Kirk Pruhs

We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job J has processing length pj, weight wj, and is processed at a rate of lij when scheduled on machine i. The online scheduler knows the values of wj and lij upon arrival of the job, but is not aware of the quantity pj. We present the first online algorithm that is scalable ((1+ε)-speed O(1/2)-competitive for any constant ε > 0) for the total weighted flow-time objective. No non-trivial results were known for this setting, except for the most basic case of identical machines. Our result resolves a major open problem in online scheduling theory. Moreover, we also show that no job needs more than a logarithmic number of migrations. We further extend our result and give a scalable algorithm for the objective of minimizing total weighted flow-time plus energy cost for the case of unrelated machines. In this problem, each machine can be sped up by a factor of f-1i(P) when consuming power P, where fi is an arbitrary strictly convex power function. In particular, we get an O(γ2)-competitive algorithm when all power functions are of form sγ. These are the first non-trivial non-clairvoyant results in any setting with heterogeneous machines. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. This has a spirit similar to coordination mechanisms that attempt to achieve near optimum welfare in the presence of selfish agents (jobs). To the best our knowledge, this is the first work that demonstrates the usefulness of ideas from coordination mechanisms and Nash equilibria for designing and analyzing online algorithms.

SODA Conference 2012 Conference Paper

Online scheduling with general cost functions

• Sungjin Im
• Benjamin Moseley
• Kirk Pruhs

SODA Conference 2012 Conference Paper

Scheduling heterogeneous processors isn't as easy as you think

• Anupam Gupta 0001
• Sungjin Im
• Ravishankar Krishnaswamy
• Benjamin Moseley
• Kirk Pruhs

FOCS Conference 2011 Conference Paper

Green Computing Algorithmics

• Kirk Pruhs

The converging trends of society's desire/need for more sustainable technologies, exponentially increasing power densities within computing devices, and exponentially more computing devices, have inevitably pushed power and energy management into the forefront of computing design and management for purely economic reasons. Thus we are in the midst of a green computing revolution involving the redesign of information technology hardware and software at all levels of the information technology stack. This revolution has spawned a multitude of technological challenges, many of which are algorithmic in nature. We provide pointers into the literature on the green computing algorithmics.

FOCS Conference 2010 Conference Paper

The Geometry of Scheduling

• Nikhil Bansal 0001
• Kirk Pruhs

We consider the following general scheduling problem: The input consists of n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow, weighted tardiness, and sum of flow squared. The main contribution of this paper is a randomized polynomial-time algorithm with an approximation ratio O(log log n P), where P is the maximum job size. We also give an O(1) approximation in the special case when all jobs have identical release times. Initially, we show how to reduce this scheduling problem to a particular geometric set-cover problem. We then consider a natural linear programming formulation of this geometric set-cover problem, strengthened by adding knapsack cover inequalities, and show that rounding the solution of this linear program can be reduced to other particular geometric set-cover problems. We then develop algorithms for these sub-problems using the local ratio technique, and Varadarajan's quasi-uniform sampling technique. This general algorithmic approach improves the best known approximation ratios by at least an exponential factor (and much more in some cases) for essentially all of the nontrivial common special cases of this problem. We believe that this geometric interpretation of scheduling is of independent interest.

SODA Conference 2009 Conference Paper

Scalably scheduling processes with arbitrary speedup curves

• Jeff Edmonds
• Kirk Pruhs

We give a scalable ((1+ ∊ )-speed O (1)-competitive) non-clairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.

TCS Journal 2009 Journal Article

Speed scaling with a solar cell

• Nikhil Bansal
• Ho-Leung Chan
• Kirk Pruhs

We consider the setting of a device that obtains its energy from a battery and some regenerative source such as a solar cell. We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes, so as to minimize the energy recharge rate of the regenerative source. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We show that, using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is O ( 1 ) -competitive with respect to recharge rate.

SODA Conference 2009 Conference Paper

Speed scaling with an arbitrary power function

• Nikhil Bansal 0001
• Ho-Leung Chan
• Kirk Pruhs

TCS Journal 2007 Journal Article

Approximation schemes for a class of subset selection problems

• Kirk Pruhs
• Gerhard J. Woeginger

In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time.

FOCS Conference 2007 Conference Paper

Non-Preemptive Min-Sum Scheduling with Resource Augmentation

• Nikhil Bansal 0001
• Ho-Leung Chan
• Rohit Khandekar
• Kirk Pruhs
• Cliff Stein 0001
• Baruch Schieber

We give the first O(l)-speed O(l) approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(l)-speed O(l)-approximations for the non-preemptive scheduling problems; l|r j | Sigmaw j F j (weighted flow time), l |r j | SigmaT j (total tardiness), the broadcast version of 1 |r j | Sigmaw j F j, an O(I)-speed, 1-approximation for l |r j | Sigma U macr j (throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |r j | Sigmaw j T j (weighted tardiness). Our main contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.

SODA Conference 2007 Conference Paper

Speed scaling for weighted flow time

• Nikhil Bansal 0001
• Kirk Pruhs
• Cliff Stein 0001

FOCS Conference 2006 Conference Paper

Balanced Allocations of Cake

• Jeff Edmonds
• Kirk Pruhs

We give a randomized algorithm for the well known caking cutting problem that achieves approximate fairness, and has complexity O(n), when all players are honest. The heart of this result involves extending the standard offline multiple-choice balls and bins analysis to the case where the underlying resources/bins/machines have different utilities to different players/balls/jobs

SODA Conference 2006 Conference Paper

Cake cutting really is not a piece of cake

• Jeff Edmonds
• Kirk Pruhs

SODA Conference 2004 Conference Paper

A maiden analysis of Longest Wait First

• Jeff Edmonds
• Kirk Pruhs

FOCS Conference 2004 Conference Paper

Dynamic Speed Scaling to Manage Energy and Temperature

• Nikhil Bansal 0001
• Tracy Kimbrel
• Kirk Pruhs

We first consider online speed scaling algorithms to minimize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power required to run at speed s is P(s) = s/sup /spl alpha//. We provide a tight /spl alpha//sup /spl alpha// bound on the competitive ratio of the previously proposed optimal available algorithm. This improves the best known competitive ratio by a factor of 2/sup /spl alpha//. We then introduce an online algorithm, and show that this algorithm's competitive ratio is at most 2(/spl alpha//(/spl alpha/ - 1))/sup /spl alpha//e/sup /spl alpha//. This competitive ratio is significantly better and is approximately 2e/sup /spl alpha/+1/ for large /spl alpha/. Our result is essentially tight for large /spl alpha/. In particular, as /spl alpha/ approaches infinity, we show that any algorithm must have competitive ratio e/sup /spl alpha// (up to lower order terms). We then turn to the problem of dynamic speed scaling to minimize the maximum temperature that the device ever reaches, again subject to the constraint that all jobs finish by their deadlines. We assume that the device cools according to Fourier's law. We show how to solve this problem in polynomial time, within any error bound, using the ellipsoid algorithm.

TCS Journal 2004 Journal Article

Semi-clairvoyant scheduling

• Luca Becchetti
• Stefano Leonardi
• Alberto Marchetti-Spaccamela
• Kirk Pruhs

In (Symp. Discrete Algorithms 2002, p. 762) it was shown that the obvious semi-clairvoyant generalization of the Shortest Processing Time is O(1)-competitive with respect to average stretch on a single machine. In (Symp. Discrete Algorithms 2002, p. 762) it was left as an open question whether it was possible for a semi-clairvoyant algorithm to be O(1)-competitive with respect to average flow time on a single machine. Here we settle this open question by giving a semi-clairvoyant algorithm that is O(1)-competitive with respect to average flow time on a single machine. We also show a semi-clairvoyant algorithm on parallel machines that achieves up to constant factors the best known competitive ratio for clairvoyant on-line algorithms. In some sense one might conclude from this that the QoS achievable by semi-clairvoyant algorithms is competitive with clairvoyant algorithms. We finally show that, in contrast to the clairvoyant case, no semi-clairvoyant algorithm can be simultaneously O(1)-competitive with respect to average stretch and O(1)-competitive with respect to average flow time.

STOC Conference 2003 Conference Paper

Server scheduling in the L p norm: a rising tide lifts all boat

• Nikhil Bansal 0001
• Kirk Pruhs

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern of that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is optimize the L p metric, 1 < p < ∞ . Thus we consider server scheduling strategies to optimize the L p norms of the standard QoS measures, flow and stretch. We first show that there is no n o(1) -competitive online algorithm for the L p norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, SJF and SRPT , are O(1+ε) -speed O(1/ε) -competitive for the L p norms of flow and stretch. And that the standard nonclairvoyant algorithm for optimizing average QoS, SETF , is O(1+ε) -speed O(1/ε (2+2/p) ) -competitive for the L p norms of flow. These results argue that these standard algorithms will not starve jobs until the system is near peak capacity. In contrast, we show that the Round Robin, or Processor Sharing algorithm, which is sometimes adopted because of its seeming fairness properties, is not O(1+ε) -speed n o(1) -competitive for sufficiently small ε .

SODA Conference 2002 Conference Paper

Broadcast scheduling: when fairness is fine

• Jeff Edmonds
• Kirk Pruhs

SODA Conference 1999 Conference Paper

Eliminating Migration in Multi-Processor Scheduling

• Bala Kalyanasundaram
• Kirk Pruhs

FOCS Conference 1997 Conference Paper

Minimizing Flow Time Nonclairvoyantly

• Bala Kalyanasundaram
• Kirk Pruhs

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average response/flow time. This is the classic CPU scheduling problem faced by time sharing operating systems. In the standard 3-field scheduling notation this is the nonclairvoyant version of 1|pmtn, r/sub j/|/spl Sigma/F/sub j/. Its easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst n-competitive, where n is the number of jobs. Yet there is no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably o(n). We present a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio /spl theta/(lognloglogn) against an adaptive adversary. RMLF is a slight variation of the multi level feedback (MLF) algorithm used by the Unix operating system, further justifying the adoption of this algorithm. R. Motwani et al. (1994) showed that every randomized nonclairvoyant algorithm is /spl Omega/2(log n)competitive, and that every deterministic nonclairvoyant algorithm is /spl Omega/2(n/sup 1/3/)-competitive.

FOCS Conference 1995 Conference Paper

Speed is as Powerful as Clairvoyance

• Bala Kalyanasundaram
• Kirk Pruhs

We consider several well known nonclairvoyant scheduling problems, including the problem of minimizing the average response time, and best-effort firm real-time scheduling. It is known that there are no deterministic online algorithms for these problems with bounded (or even polylogarithmic in the number of jobs) competitive ratios. We show that moderately increasing the speed of the processor used by the non-clairvoyant scheduler effectively gives this scheduler the power of clairvoyence. Furthermore, we show that there exist online algorithms with bounded competitive ratios on all inputs that are not closely correlated with processor speed.

STOC Conference 1994 Conference Paper

Fault-tolerant scheduling

• Bala Kalyanasundaram
• Kirk Pruhs

TCS Journal 1994 Journal Article

Not all insertion methods yield constant approximate tours in the Euclidean plane

• Vineet Bafna
• Bala Kalyanasundaram
• Kirk Pruhs

An insertion heuristic for the traveling salesman problem adds cities iteratively to an existing tour by replacing one edge with a two-edge path through the new city in the cheapest possible way. Rosenkrantz (1977) asked whether every order of inserting vertices gives a constant-factor approximation algorithm. We answer this question by showing that for some point sets, there is an order that yields tours with length Ω(log n⧸log logn) times optimum, even if the underlying metric space is the Euclidean plane.

SODA Conference 1991 Conference Paper

On-Line Weighted Matching

• Bala Kalyanasundaram
• Kirk Pruhs

I&C Journal 1991 Journal Article

The complexity of controlled selection

• Kirk Pruhs
• Udi Manber

We identify a class of problems, called controlled selection problems, and study their complexity. A controlled selection problem involves a random selection of a sample from a large set subject to certain structural constraints. The structural constraints model some desired relationships among the elements of the set, which we want to preserve under random selection. For example, the set may be divided into equivalence classes and we may want to ensure that not too many elements are chosen from the same class, or the set may correspond to vertices of a graph and we may want to ensure that the sample does not induce a cycle. Controlled selection problems arise in many disciplines, including statistics, mathematical programming, combinatorial algorithms, and resource allocation. This is the first attempt to unify them. We develop techniques for determining the complexity of controlled selection problems given the structural constraints. We use these techniques to determine the complexity of many types of controlled selection problems. We show that a controlled selection problem is polynomial-time reducible to the problem of finding a maximum weight sample satisfying the structural constraints. We also show that a general reduction in the opposite direction would imply that one-way functions do not exist. In contrast, we show that most natural controlled selection problems have the same complexity (within polynomial time) as the problem of finding a maximum weight sample satisfying the structural constraints. We also present efficient algorithms for several controlled selection problems.