We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the "standard" model, in which an algorithm is allowed to swap the requested item with previous items for free. We construct an online algorithm Full-Or-Partial-Move (FPM), whose competitive ratio is at most 3.3904, improving over the previous best known bound of 4.

We break the barrier of $3/2$ for the problem of online load balancing with known makespan, also known as bin stretching. In this problem, $m$ identical machines and the optimal makespan are given. The load of a machine is the total size of all the jobs assigned to it and the makespan is the maximum load of all the machines. Jobs arrive online and the goal is to assign each job to a machine while staying within a small factor (the competitive ratio) of the optimal makespan. We present an algorithm that maintains a competitive ratio of $139/93<1.495$ for sufficiently large values of $m$, improving the previous bound of $3/2$. The value 3/2 represents a natural bound for this problem: as long as the online bins are of size at least $3/2$ of the offline bin, all items that fit at least two times in an offline bin have two nice properties. They fit three times in an online bin and a single such item can be packed together with an item of any size in an online bin. These properties are now both lost, which means that putting even one job on a wrong machine can leave some job unassigned at the end. It also makes it harder to determine good thresholds for the item types. This was one of the main technical issues in getting below $3/2$. The analysis consists of an intricate mixture of size and weight arguments.

Speed-robust scheduling is the following two-stage problem of scheduling $n$ jobs on $m$ uniformly related machines. In the first stage, the algorithm receives the value of $m$ and the processing times of $n$ jobs; it has to partition the jobs into $b$ groups called bags. In the second stage, the machine speeds are revealed and the bags are assigned to the machines, i.e., the algorithm produces a schedule where all the jobs in the same bag are assigned to the same machine. The objective is to minimize the makespan (the length of the schedule). The algorithm is compared to the optimal schedule and it is called $ρ$-robust, if its makespan is always at most $ρ$ times the optimal one. Our main result is an improved bound for equal-size jobs for $b=m$. We give an upper bound of $1.6$. This improves previous bound of $1.8$ and it is almost tight in the light of previous lower bound of $1.58$. Second, for infinitesimally small jobs, we give tight upper and lower bounds for the case when $b\geq m$. This generalizes and simplifies the previous bounds for $b=m$. Finally, we introduce a new special case with relatively small jobs for which we give an algorithm whose robustness is close to that of infinitesimal jobs and thus gives better than $2$-robust for a large class of inputs.

Abstract. In the online packet scheduling problem with deadlines ([Formula: see text], for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a nonnegative weight, which represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning [Formula: see text] that has been a subject of intensive study since 2001 is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a [Formula: see text]-competitive online algorithm for [Formula: see text] (where [Formula: see text] is the golden ratio), matching the previously established lower bound.

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ-competitive online algorithm for PacketScheduling (where ϕ ≈ 1.618 is the golden ratio), matching the previously established lower bound.

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of ϕ≈1.618 [11], [2], [6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of ϕ applies even to the special case of 2-bounded instances, and a ϕ-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a ϕ-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 12(13−1)≈1.303 and we prove a nearly tight lower bound of 14(1+17)≈1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer ℓ≥0 we prove a lower bound of 12(ℓ+1)(1+5+8ℓ+4ℓ2) for online algorithms with ℓ-lookahead, i.e., algorithms that at time t can see all packets arriving by time t+ℓ. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with ℓ-lookahead, for any ℓ≥0.

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.

We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on $$m$$ uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a lower bound of $$m$$ on the competitive ratio for scheduling unit weight jobs with varying sizes, which is tight. For unit size and weight we show that a natural greedy algorithm is $$4/3$$ -competitive and optimal on $$m=2$$ machines, while for large $$m$$ , its competitive ratio is between $$1.56$$ and $$2$$ . Furthermore, no algorithm is better than $$1.5$$ -competitive.

We investigate the online variant of the (Multiple) Knapsack Problem: an algorithm is to pack items, of arbitrary sizes and profits, in k knapsacks (bins) without exceeding the capacity of any bin. We study two objective functions: the sum and the maximum of profits over all bins. With either objective, our problem statement captures and generalizes previously studied problems, e.g. Dual Bin Packing [ 1 , 6 ] in case of the sum and Removable Knapsack [ 10 , 11 ] in case of the maximum. Following previous studies, we consider two variants, depending on whether the algorithm is allowed to remove items (forever) from its bins or not, and two special cases where the profit of an item is a function of its size, in addition to the general setting. We study both deterministic and randomized algorithms; for the latter, we consider both the oblivious and the adaptive adversary model. We classify each variant as either admitting O (1)-competitive algorithms or not. We develop simple O (1)-competitive algorithms for some cases of the max-objective variant believed to be intrac because only 1-bin deterministic algorithms were considered before.

We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.

The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer ρ has a fixed cost cρ. In addition, we incur waiting costs for each order, possibly an arbitrary non-decreasing function of time, different for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1.8. This ratio can be reduced to ≈ 1.574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is ℙ -hard and that the natural linear program for JRP has integrality gap at least 1.245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio ≈ 1.791, breaking the barrier of 1.8. We also show that the integrality gap of the linear program for JRP-L is at least 12/11 ≈ 1.09. In the online case, we show a lower bound of ≈ 2.754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2.64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.

In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins. Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins. Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

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 semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.

In queue-based scheduling systems jobs are executed according to a predefined sequential plan. During exe- cution, faults may occur that cause jobs to re-execute, thus delaying the whole schedule. It is thus important to determine (in real-time) whether the given set of pre- ordered jobs is fault-tolerant, that is, if all jobs will al- ways meet their deadlines. This allows, for instance, to decide online whether to admit a new urgent job into the queue while still guaranteeing that the whole sched- ule remains fault-tolerant. Our goal in this work is to design efficient algorithm for testing fault tolerance of sequenced jobs in the presence of transient faults. We consider different fault models that specify which fault patterns are allowed to occur and how soon failed jobs can be restarted. For each fault model we provide ef- ficient algorithms that determine the feasibility of all jobs in the schedule. Our algorithms are exact and run in time linear in the number of jobs (deterministically, or with very high probability, depending on the fault model), and thus can be used to make real-time deci- sions.

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 single‐processor nonpreemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below 2 and show several lower bounds on the competitive ratios. First, we give a barely random $5/3$‐competitive algorithm that uses only one random bit. We also show a lower bound of $3/2$ on the competitive ratio of barely random algorithms that randomly choose one of two deterministic algorithms. If the two algorithms are selected with equal probability, we can further improve the bound to $8/5$. Second, we give a deterministic $3/2$‐competitive algorithm in the model that allows restarts, and we show that in this model the ratio $3/2$ is optimal. For randomized algorithms with restarts we show a lower bound of $6/5$.

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 weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 ≈ 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio ≈ 1.377 and a matching lower bound.

We study the computational complexity of training a single spiking neuron N with binary coded inputs and output that, in addition to adaptive weights and a threshold, has adjustable synaptic delays. A synchronization technique is introduced so that the results concerning the nonlearnability of spiking neurons with binary delays are generalized to arbitrary real-valued delays. In particular, the consistency problem for N with programmable weights, a threshold, and delays, and its approximation version are proven to be NP-complete. It follows that the spiking neurons with arbitrary synaptic delays are not properly PAC learnable and do not allow robust learning unless RP = NP. In addition, the representation problem for N, a question whether an n-variable Boolean function given in DNF (or as a disjunction of O(n) threshold gates) can be computed by a spiking neuron, is shown to be coNP-hard.

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 in the partition. This problem is NP-hard, even for a special case, denoted 2-MCSP, where each letter occurs at most twice in each input string. We study a greedy algorithm for MCSP that at each step extracts a longest common substring from the given strings. We show that the approximation ratio of this algorithm is between Ω( n 0.43 ) and O ( n 0.69 ). In the case of 2-MCSP, we show that the approximation ratio is equal to 3. For 4-MCSP, we give a lower bound of Ω(log n ).

In dial-a-ride problems, items have to be transported from a source to a destination. The characteristics of the servers involved as well as the specific requirements of the rides may vary. Problems are defined on some metric space, and the goal is to find a feasible solution that minimizes a certain objective function. The structure of these problems allows for a notation similar to the standard notation for scheduling and queueing problems. We introduce such a notation and show how a class of 7,930 dial-a-ride problem types arises from this approach. In examining their computational complexity, we define a partial ordering on the problem class and incorporate it in the computer program DARCLASS. As input DARCLASS uses lists of problems whose complexity is known. The output is a classification of all problems into one of three complexity classes: solvable in polynomial time, NP-hard, or open. For a selection of the problems that form the input for DARCLASS, we exhibit a proof of polynomial-time solvability or NP-hardness.

The notion of traitor tracing was introduced by Chor, Fiat, and Naor [Tracing Traitors, Lecture Notes in Comput. Sci. 839, 1994, pp. 257--270] in order to combat piracy scenarios. Recently, Fiat and Tassa [ Tracing Traitors, Lecture Notes in Comput. Sci. 1666, 1999, pp. 354--371] proposed a dynamic traitor tracing scenario, in which the algorithm adapts dynamically according to the responses of the pirate. Let n be the number of users and p the number of traitors. Our main result is an algorithm which locates p traitors, even if p is unknown, using a watermarking alphabet of size p+1 and an optimal number of $\Theta(p^2 + p\log n)$ rounds. This improves the exponential number of rounds achieved by Fiat and Tassa in this case. We also present two algorithms that use a larger alphabet: for an alphabet of size p+c+1, $c\geq1$, an algorithm that uses O(p 2 /c+ p log n) rounds; for an alphabet of size pc+1, an algorithm that uses O(p log c n ) rounds. Our final result is a lower bound of $\Omega(p^2/c+p\log_{c+1}n)$ rounds for any algorithm that uses an alphabet of size p+c, assuming that p is not known in advance.

We consider a version ofmultiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a set of n jobs, with each job characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs. The main result is a $1+\phi\approx 2.618$ competitive algorithm for the on-line version of the problem, where $\phi$ is the golden ratio. A matching lower bound shows that this is the best possible algorithm working for all m. For fixed m we give improved bounds; in particular, for $m=2$ we give a $\phi\approx 1.618$ competitive algorithm, which is best possible. For the off-line problem we present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Moreover, we present an approximation algorithm which runs in time $O(n\log n)$ for arbitrary m and guarantees a $2-\frac{1}{m}$ approximation ratio.

We investigate two methods for proving lower bounds on the size of small-depth circuits, namely the approaches based on multiparty communication games and algebraic characterizations extending the concepts of the tensor rank and rigidity of matrices. Our methods are combinatorial, but we think that our main contribution concerns the algebraic concepts used in this area (tensor ranks and rigidity). Our main results are following. (i) An $o(n)$-bit protocol for a communication game for computing shifts, which also gives an upper bound of $o(n^2)$ on the contact rank of the tensor of multiplication of polynomials; this disproves some earlier conjectures. A related probabilistic construction gives an $o(n)$ upper bound for computing all permutations and an $O(n\log\log n)$ upper bound on the communication complexity of pointer jumping with permutations. (ii) A lower bound on certain restricted circuits of depth 2 which are related to the problem of proving a superlinear lower bound on the size of logarithmic-depth circuits; this bound has interpretations both as a lower bound on the rigidity of the tensor of multiplication of polynomials and as a lower bound on the communication needed to compute the shift function in a restricted model. (iii) An upper bound on Boolean circuits of depth 2 for computing shifts and, more generally, all permutations; this shows that such circuits are more efficient than the model based on sending bits along vertex-disjoint paths.

We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested...

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented.>

The problem of online job scheduling on various parallel architectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given.>