Research

I am a theoretical computer scientist, meaning that I like to prove things about computational problems and the algorithms used to solve them. (I have also done some empirical work on processor allocation, a problem that does not lend itself to theoretical analysis.) My research has primarily focused on scheduling problems, but I like other problems as well and have publications in the following areas:

For a chronological listing of my publications, check out my list of publications.

Scheduling

In classical scheduling problems, the algorithm is given a list of jobs to complete and must decide when to run them for the best user experience. (Although scheduling problems are nearly always phrased in terms of "jobs" run on "machines", the results apply equally well to other applications, like people scheduling errands.) In general, the jobs arrive over time so that not all of them are available at the start of the problem. The metric I am most interested in is total flow, which is the sum of job completion times minus the sum of job arrival times. (It is useful to think of the flow of a job as the time between its arrival and completion. Then, the total flow is the sum of the individual job flows.) Minimizing this metric is exactly minimizing the sum of the times that users are waiting for their jobs. My very first theoretical result was to show that a natural algorithm is the best possible online algorithm. (An algorithm is online if makes decisions as the input arrives rather than receiving the input all at once the way an offline algorithm does.)

More recently, I've been looking at variations of scheduling that require choices other than when to schedule each job. For example, one recent result addresses scheduling with rejections, where some of the jobs can be rejected at a cost. The metric is then total flow plus the cost of rejected jobs. One example of this is managing a "TO DO" list where jobs can either be scheduled or delegated to someone else. In this example, each item on the TO DO list has two parameters, how long it will take you to complete and how long it will take someone else. You can only work on one task at a time, but work on the tasks that are delegated to someone else proceed at the same time. (Think of having a lot of coworkers that can work on delegated tasks.) Thus, delegating some tasks may reduce the sum of completion times even when each task takes you less time than your coworkers.

I give both algorithms and hardness results, mostly for the special case when all jobs have unit length.

Another situation where the scheduling algorithm needs to make another type of choice is power-aware scheduling. Consider the problem of scheduling a laptop with a limited battery capacity. The processor can run at different speeds and it uses more energy the faster it runs. My most recent work has considered the question of how to schedule such a processor to get the best possible performance out of the laptop's limited battery capacity.

Processor allocation

Processor allocation is about answering the question "Which free processors should be assigned to the next job?" for jobs run on supercomputers. This question is separate from the question of when to run jobs; the allocator is given a job with instructions to put it on the machine immediately. Intuitively, the best allocation will use processors that are close together since this shortens the time necessary to send messages between processors assigned to the same job. We give several algorithms based on this intuition and evaluate them both theoretically and with experiments.

I began this work while an intern at Sandia National Labs. The allocator has also been licensed to Cray and is in use on a number of supercomputers around the world.

Admission control

Admission control problems involve choosing a subset of a large number of requests to satisfy with limited resources. The prototypical example is a network receiving requests for dedicated bandwidth between pairs of nodes; each link has limited bandwidth so some of the requests might need to be rejected. The quality of an admission control algorithm can be measured by how well it maximizes the value of accepted requests or by how well it minimizes the value of rejected requests. Note that an optimal solution gives the best possible value for both criteria, but an algorithm that does well by one criteria may not do well according to the other. For example, suppose algorithm A always accepts at least half as many requests as the optimal solution while algorithm R always rejects no more than twice as many requests as the optimal solution. Which should you use? The answer depends on how well the optimal solution does. On one hand, if the optimal solution accepts 98% of the requests (rejecting 2%), you should use algorithm R since it will accept at least 96% of the requests while algorithm A might accept only 49% of them. On the other hand, if the optimal solution accepts only 50% of the requests (rejecting 50% of them), then you should use algorithm A since it will accept at least 25% of the requests while algorithm R might reject them all.

My work involves giving a way to combine the different types of algorithms. We give a procedure whose input is one algorithm with guaranteed quality with respect to acceptances and one with guaranteed quality with respect to rejections. The procedure gives algorithm that provides a guarantee with respect to both measures simultaneously.

Algorithmic questions in graph theory

Graph theory studies graphs, objects consisting of vertices and edges, where each edge joins a pair of vertices. Algorithmic graph theory studies the design of algorithms to determine whether a graph has some desired property. One example of my work in this area is graph pebbling, which models moving resources around in a way that consumes some of them. Think of delivering gasoline with a truck; the further the truck travels to its destination, the less gas it delivers upon arrival. (Graph pebbling was developed to provide tools for problems in number theory, but my interest in it comes entirely from this idea of strategies for moving resources.) The resources are modeled with pebbles placed on the vertices of a graph. A pebbling move takes two pebbles off some vertex and places one on a neighbor of that vertex. Basic questions in the field are "How many pebbles must be placed on a graph so that a pebble can reach any vertex?" and "How many pebbles guarantee that a pebble can reach any vertex from any arrangement?". For the first question, we give a number of bounds based on the graph's girth and minimum degree. For the second question, we give short proofs of some prior results on paths, cycles, trees, and hypercubes, plus an algorithm to compute the value for a tree. For an overview of other results in this relatively new field, check out the survey maintained by Glenn Hurlbert.

More recently, I worked on a problem we call parity-edge coloring. This problem aims to assign colors to edges so that every path has some color appearing an odd number of times. The original motivation was finding embeddings in the hypercube, but we quickly found that the problem has interesting mathematical structure in its own right. In particularly, we believe that the number of colors required to parity-edge color Kn, the complete graph on n vertices, is one less than n rounded to the next highest power of 2, i.e. 2ceil(lg n)-1. We introduce this parameter and prove some properties of it, including that 2ceil(lg n)-1 is the correct value for a slight variation on the problem.

In addition, I have a minor result on distance-2 edge coloring a graph. This means assigning colors to the edges of a graph so that no adjacent edges are assigned the same color and no edge is adjacent to a pair of edges with the same color. (This is also called strong edge coloring.) We show that finding a coloring using the minimum number of colors is NP-hard even on a restricted class of graphs. (NP-hardness means that it is unlikely that large instances of the problem can be solved in a reasonable amount of time.)

Return to David Bunde's home page
Last modified August 2007 by dbunde@knox.edu