Semi-Online Preemptive Scheduling: One Algorithm for All Variants (2009)
We present a unified optimal semi-online algorithm for preemptive schedul- ing on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of...
Semi-Online Preemptive Scheduling: One Algorithm for All Variants (2009)
We present a unified optimal semi-online algorithm for preemptive schedul- ing on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of...
Semi-Online Preemptive Scheduling: One Algorithm for All Variants (2009)
We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of...
Fairness-Free Periodic Scheduling (2008)
Jiri Sgall, Hadas Shachnai, Tami Tamir
We consider a problem of repeatedly scheduling n jobs on m parallel machines. Each job is associated with a profit, gained each time the job is completed, and the goal is to maximize the average...
Improved Online Algorithms for Buffer Management in QoS Switches (2007)
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy
We consider the following buffer management problem arising in QoS networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total value...
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help (2007)
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a...
On-Line Scheduling on Parallel Machines (2006)
Given a parallel machine with processors arranged in some particular network topology (e.g., on a mesh machine the processors are arranged in a rectangular grid), we have to execute different...
We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques...
A Simple Combinatorial Proof of Duality of Multiroute Flows and Cuts (2004)
Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, Jiri Sgall
A classical flow is a nonnegative linear combination of unit flows along simple paths. A multiroute flow, first considered by Kishimoto and Takeuchi, generalizes this concept. The basic building...
Markus Bläser, Bodo Manthey, Jiri Sgall
We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ ∈ [½, 1). That means, the edge weights fulfill w(u, v)...
Improved Online Algorithms for Buffer Management in QoS Switches (2004)
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy
We consider the following buffer management problem arising in QoS networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total value...
The Greedy Algorithm for the Minimum Common String Partition Problem (2004)
Marek Chrobak, Petr Kolman, Jiri Sgall
In the Minimum Common String Partition problem (MCSP) we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings...
The Greedy Algorithm for the Minimum Common String Partition Problem (2004)
Marek Chrobak, Petr Kolman, Jiri Sgall
In the Minimum Common String Partition problem (MCSP) we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings...
A Simple Combinatorial Proof of Duality of Multiroute Flows and Cuts (2004)
Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, Jiri Sgall
A classical flow is a nonnegative linear combination of unit flows along simple paths. A multiroute flow, first considered by Kishimoto and Takeuchi, generalizes this concept. The basic building...
Preemptive Scheduling in Overloaded Systems (2003)
Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob Van Stee, Tomas Tichy, ...
The following scheduling problem is studied: We are given a set of tasks with release times, deadlines, and profit rates. The objective is to determine a 1-processor preemptive schedule of the given...
Coloring Graphs from Lists with Bounded Size of Their Union (2003)
A graph G is k-choosable if its vertices can be colored from any lists L(v) of colors with jL(v)j k for all v 2 V (G). A graph G is said to be (k; u)-choosable if its vertices can be colored from any...
Preemptive Scheduling in Overloaded Systems (2002)
Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob Van Stee, Tomas Tichy, ...
The following scheduling problem is studied: We are given a set of tasks with release times, deadlines, and profit rates. The objective is to determine a 1-processor preemptive schedule of the given...
Marek Chrobak, Janos Csirik, Csanad Imreh, John Noga, Jiri Sgall, Gerhard J. Woeginger
We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. The term "conflict" refers to a situation where two or more processors share common...
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines (1999)
We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion...
Competitive Analysis of Call Admission Algorithms that Allow Delay. (1998)
Feldmann, Anja, Maggs, Bruce, Sgall, Jiri, Sleator, Daniel D., Tomkins, Andrew
This paper presents an analysis of several simple on-line algorithms for processing requests for connections in distributed networks. These algorithms are called call admission algorithms. Each...
A Lower Bound for Randomized On-Line Multiprocessor Scheduling (1997)
We significantly improve the previous lower bounds on the performance of randomized algorithms for on-line scheduling jobs on m identical machines. We also show that a natural idea for constructing...
Solution Of A Covering Problem Related To Labelled Tournaments (1996)
Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of...
Competitive Analysis of Call Admission Algorithms that Allow Delay (1995)
Anja Feldmann, Bruce Maggs, Jiri Sgall, Daniel D. Sleator, Andrew Tomkins
This paper presents an analysis of several on-line algorithms, called call admission algorithms, for processing requests for connections in distributed networks. Each request comes with a source, a...
On The Computational Power of DNA (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...
Making DNA Computers Error Resistant (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We describe methods for making volume decreasing algorithms more resistant to certain types of errors. Such error recovery techniques are crucial if DNA computers ever become practical. Our first...
On the Computational Power of DNA
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion...