Online C-benevolent job scheduling on multiple machines

We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized \((2+2/{\hbox {m}})\)-competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.     

Railway delay management with passenger rerouting considering train capacity constraints

Delay management for railways is concerned with the question of whether a train should wait for a delayed feeder train or depart on time. The answer should not only depend on the length of the delay but also consider other factors, such as capacity restrictions. We present an optimization model for delay management in railway networks that accounts for capacity constraints on the number of passengers that a train can effectively carry. While limited capacities of tracks and stations have been considered in delay management models, passenger train capacity has been neglected in the literature so far, implicitly assuming an infinite train capacity. However, even in open systems where no seat reservation is required and passengers may stand during the journey if all seats are occupied, physical space is naturally limited, and the number of standing seats is constrained for passenger safety reasons. We present a mixed-integer nonlinear programming formulation for the delay management problem with passenger rerouting and capacities of trains. Our model allows the rerouting of passengers missing their connection due to delays or capacity constraints. We linearize the model in exact and approximate ways and experimentally compare the different approaches with the solution of a reference model from the literature that neglects capacity constraints. The results demonstrate that there is a significant impact of considering train capacity restrictions in decisions to manage delays.     

Bounded delay packet scheduling in a bounded buffer

We study buffer management in QoS-enabled network switches in the bounded delay model where each packet has a weight and a deadline. We consider the more realistic situation where the switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers. Recently, for the single buffer case, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm were found. We give a simple deterministic 2-competitive algorithm for the single buffer case.     

Online competitive algorithms for maximizing weighted throughput of unit jobs

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios.We first give a randomized algorithm RMix with competitive ratio of e/(e−1)≈1.582. This is the first algorithm for this problem with competitive ratio smaller than 2.Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf_α, whose competitive ratio on s-bounded instances is 2−2/s+o(1/s). For 3-bounded instances its ratio is ≈1.618, matching the known lower bound.In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of . Also, in the 2-uniform case, we prove a lower bound of for deterministic memoryless algorithms, matching a known upper bound.Finally, we investigate the multiprocessor case and give a -competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases.     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Online algorithms with advice for the dual bin packing problem

This paper studies the problem of maximizing the number of items packed into n bins, known as the dual bin packing problem, in the advice per request model. In general, no online algorithm has a constant competitive ratio for this problem. An online algorithm with 1 bit of advice per request is shown to be 3/2-competitive. Next, for \(0< \varepsilon < 1{/}2\), an online algorithm with advice that is \((1/(1-\varepsilon ))\)-competitive and uses \({O}(1/\varepsilon )\) bits of advice per request is presented.     

Oscillation of second order neutral delay differential equations of Emden-Fowler type

We present new oscillation criteria for the second order nonlinear neutral delay differential equation [y(t)-py(t-τ)]'+ q(t)y ^λ (g(t)) sgn y(g(t)) = 0, t ≧ t ₀. Our results solve an open problem posed by James S.W . Wong [24]. The relevance of our results becomes clear due to a carefully selected example. This revised version was published online in June 2006 with corrections to the Cover Date.     

Competitive Algorithms for Relaxed List Update and Multilevel Caching

We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x_j is c_j, where c_i ≤ c_{i + 1} for all i. After the access, x_j can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by Aggarwal et al. (1987, “Proc. 19th Symp. Theory of Computing,” pp. 305–313) as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is C-competitive, for some C, for a restricted class of cost functions. We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. We prove that move-to-front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP.     

Optimal Stochastic Impulse Control with Delayed Reaction

We study impulse control problems of jump diffusions with delayed reaction. This means that there is a delay δ>0 between the time when a decision for intervention is taken and the time when the intervention is actually carried out. We show that under certain conditions this problem can be transformed into a sequence of iterated no-delay optimal stopping problems and there is an explicit relation between the solutions of these two problems. The results are illustrated by an example where the problem is to find the optimal times to increase the production capacity of a firm, assuming that there are transaction costs with each new order and the increase takes place δ time units after the (irreversible) order has been placed.     

A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

Extension of algorithm list scheduling for a semi-online scheduling problem

A general algorithm, called ALG, for online and semi-online scheduling problem Pm||C _max with m ≥ 2 is introduced. For the semi-online version, it is supposed that all job have their processing times within the interval [p, rp], where p > 0,1 < r ≤ m/m − 1. ALG is a generalization of LS and is optimal in the sense that there is not an algorithm with smaller competitive ratio than that of ALG.     

Not collapsing cardinals ≤<Emphasis Type="Italic">κ</Emphasis> in (<<Emphasis Type="Italic">κ</Emphasis>)-support iterations

We deal with the problem of preserving various versions of completeness in (<κ)-support iterations of forcing notions, generalizing the case “S-complete proper is preserved by CS iterations for a stationary costationaryS⊆ω ₁”. We give applications to Uniformization and the Whitehead problem. In particular, for a strongly inaccessible cardinalκ and a stationary setS⊆κ with fat complement we can have uniformization for every (A _δ :δ ∈S′),A _δ ⊆δ = supA _δ , cf (δ) = otp(A _δ ) and a stationary non-reflecting setS′⊆S (see B.8.2). Research supported by The German-Israeli Foundation for Scientific Research & Development Grant No. G-294.081.06/93 and by The National Science Foundation Grant No. 144-EF67. Publication No. 587.     

Online facility location with facility movements

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than \({(\sqrt{13}+1)/4\approx 1.1514}\) exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.     

An approximate solution algorithm for the one-dimensional online median problem

The online median problem consists in finding a sequence of incremental solutions of the k-median problem with k increasing. A particular case of the problem is considered: the clients and facilities are located on the real line. The best algorithm available for the one-dimensional case has competitive ratio 8. We give an improved 5.83-competitive algorithm.     

Facets with fixed defect of the stable set polytope

The stable set polytope of a graph is the convex hull of the 0-1 vectors corresponding to stable sets of vertices. To any nontrivial facet ∑ _v∈V a(v)x _v ≤b of this polytope we associate an integer δ, called the defect of the facet, by δ=∑ _v∈V a(v)-2b. We show that for any fixed δ there is a finite collection of graphs (called “basis”) such that any graph with a facet of defect δ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation. Received: September 28, 1998 / Accepted: February 24, 2000?Published online April 20, 2000     

Spectral structure of Anderson type Hamiltonians

We study self adjoint operators of the form?H _ω = H ₀ + ∑λ_ω(n) <δ _n ,·>δ _n ,?where the δ _n ’s are a family of orthonormal vectors and the λ_ω(n)’s are independently distributed random variables with absolutely continuous probability distributions. We prove a general structural theorem saying that for each pair (n,m), if the cyclic subspaces corresponding to the vectors δ _n and δ _m are not completely orthogonal, then the restrictions of H _ω to these subspaces are unitarily equivalent (with probability one). This has some consequences for the spectral theory of such operators. In particular, we show that “well behaved” absolutely continuous spectrum of Anderson type Hamiltonians must be pure, and use this to prove the purity of absolutely continuous spectrum in some concrete cases. Oblatum 27-V-1999 & 6-I-2000?Published online: 8 May 2000     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine

We consider the problem of scheduling jobs on-line on a single machine with the objective of minimizing total completion time. We assume that jobs arrive over time and that release dates are known in advance, but not the processing times. The most important result we are given in this paper is the competitive analysis of a new clairvoyant on-line algorithm for this scheduling problem. We are proving that this deterministic semi-online algorithm, called ST-, is -competitive, which beats the existing lower bound for non-clairvoyant online algorithms.