Thomas Bosman

Dario Frascaria

Neil Olver

René Sitters

Leen Stougie

Fixed-Order Scheduling on Parallel Machines

We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixed-order assumption. We also give a QPTAS for the special case of unit processing times.

Introduction

We consider an extremely simple, yet challenging, scheduling principle that arises in many logistic and service applications. Given a sequence of jobs and a set of machines, we need to dispatch the jobs one by one over the machines, where for each machine the ordering of the original sequence is preserved. Hence, each machine must handle the jobs in a first-in first-out (FIFO) order. Each job has a processing time p j and weight w j and the goal is to minimize the weighted sum of completion times, where the completion time of a job j is the total processing time of the jobs preceding j (including j) on the same machine.

The FIFO-ordering restriction is common in queuing theory, where the task assignment problem [START_REF] Harchol-Balter | On choosing a task assignment policy for a distributed server system[END_REF][START_REF] Harchol-Balter | Performance Modeling and Design of Computer Systems: Queueing Theory in Action[END_REF][START_REF] Feng | Optimal state-free, size-aware dispatching for heterogeneous M/G/-type systems[END_REF] is concerned with the same question, except that jobs arrive stochastically over time. Our problem can be seen as asking for the optimal way of dispatching jobs from a single queue over m server queues under complete information of the processing times, essentially unzipping a single queue into m queues. The reverse problem of zipping m queues into a single queue, is the classic single machine scheduling problem: 1|chains| w j C j (in the 3-field notation by Graham et al. [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF]) and can be solved efficiently by greedily selecting a prefix of jobs with largest ratio of total weight over total processing time [START_REF] Lawler | Sequencing jobs to minimize total weighted completion time subject to precedence constraints[END_REF].

In the scheduling literature, the fixed-ordering scheduling problem can be seen as a special case of scheduling problems with sequence dependent setup times, where for each pair of jobs there is a changeover cost c ij that is paid if job j is the immediate successor of job i on a machine. Such setup times occur naturally in many industrial applications [START_REF] Allahverdi | The third comprehensive survey on scheduling problems with setup times/costs[END_REF]. Our problem is precisely this, in the special case where c ij = ∞ if i is later than j in the ordering, and c ij = 0 otherwise. While the problem has received substantial attention (see [START_REF] Allahverdi | A review of scheduling research involving setup considerations[END_REF][START_REF] Allahverdi | A survey of scheduling problems with setup times or costs[END_REF][START_REF] Allahverdi | The third comprehensive survey on scheduling problems with setup times/costs[END_REF] for a comprehensive literature review), almost nothing is known from a theoretical perspective (an exception is [START_REF] Hiraishi | Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs[END_REF], but this is concerned with a rather unusual objective function). We believe our work may shed light on this more general problem.

We remark that the online version of the problem, where we need to assign a job before we get to know the next job in the sequence, does not admit a constantcompetitive algorithm. Consider, for example, two machines and a sequence of three jobs (where job 1 should be completed first and job 3 last on any machine) with p 1 = k 2 , p 2 = k, p 3 = 1 and w 1 = 1, w 2 = k and w 3 is either zero or k 3 , depending on the schedule of the first two jobs. Here, k is an arbitrarily large number. It is easy to see that a good schedule requires knowledge of the weight of job 3 before deciding whether to put jobs 1 and 2 on the same machine.

Our contribution. Scheduling problems with weighted completion times objective without ordering constraints typically admit good approximations algorithms. For identical machines there is a PTAS [START_REF] Skutella | A PTAS for minimizing the total weighted completion time on identical parallel machines[END_REF], while a slightly better than 3 2approximation [START_REF] Bansal | Lift-and-round to improve weighted completion time on unrelated machines[END_REF] for unrelated machines is known. But even simpler approaches yield a constant factor approximation. On identical machines, it is a classic result due to Kawaguchi and Kyan [START_REF] Kawaguchi | Worst case bound of an LRF schedule for the mean weighted flow-time problem[END_REF] (see [START_REF] Schwiegelshohn | An alternative proof of the Kawaguchi-Kyan bound for the Largest-Ratio-First rule[END_REF] for a modern proof) that scheduling greedily according to Smith ratio (see Section 2) is a 1+ √ 2 2 -approximation. For unrelated machines, independent rounding of both a natural time-indexed LP [START_REF] Schulz | Scheduling unrelated machines by randomized rounding[END_REF] and a (nontrivial) convex quadratic program [START_REF] Skutella | Convex quadratic and semidefinite programming relaxations in scheduling[END_REF] works, and achieve approximation ratios of 3 2 + and 3 2 respectively. Another approach is α-point scheduling [START_REF] Schulz | The power of α-points in preemptive single machine scheduling[END_REF], where jobs are sorted according to the time by which an α fraction of the job has been processed in some LP relaxation. The jobs are then scheduled greedily in that order. This method has enabled many algorithmic improvements in scheduling, since it can be modified to deal with additional complications, such as precedence constraints and release times [START_REF] Queyranne | Approximation bounds for a general class of precedence constrained parallel machine scheduling problems[END_REF].

Fixed-order scheduling appears highly resistant to all these techniques. A big obstacle is that moving even a single pair of jobs onto the same machine can have a catastrophic effect on the objective function if the order is fixed: think of a job with large processing time but minuscule weight, followed by a job with large weight and minuscule processing time. Thus in order to have any hope of a non-trivial performance guarantee, jobs must be assigned to machines in a highly dependent way. To achieve this, our approach radically departs from earlier ones.

We define an important partial order ≺: essentially, j ≺ k means that not only is j earlier than k in the FIFO ordering, but also this ordering is opposite to what would be preferred according to Smith's rule. Thus as alluded to earlier, if j ≺ k we should be particularly careful about assigning j and k to the same machine. Order the machines arbitrarily. A key idea is that at only a constant factor loss, we can restrict our attention to a class of schedules we call Smith-monotone, meaning that if j ≺ k, then j is assigned to an earlier machine (or the same machine) as the one that k is assigned to. Next, we relax the problem by computing each job's completion times partially, based only on jobs preceding it in the partial order ≺. While this potentially distorts completion times a lot, we can ensure the amortized effect is not too large by appropriately rounding weights and processing times. Finally, we formulate a new LP using these partial completion times and enforcing the strong structure imposed by Smith monotonicity. This LP can be rounded in a way that completely respects the pairwise probabilities of jobs being assigned to the same machine; Smith monotonicity is crucial here. The rounding is very appealing and natural, and can be seen an analog of α-point scheduling with respect to machine index rather than time.

Finally, we remark that for the case of unit processing times, the complexity of the problem is unknown, but it is unlikely to be APX-hard: we present a QPTAS in Section A of the appendix.

Problem Definition, Notation and NP-hardness

We have a set of identical machines M = {1, . . . , m}, each of which can process one job at a time, and a totally ordered set of jobs J = 1, ..., n, where each job j ∈ J has weight w j ∈ N and processing time p j ∈ N. Because of its frequent use we also define notation for the so called Smith ratio s j := wj pj of job j. A feasible schedule µ : J → M assigns to every job j a machine µ(j). Each machine processes the jobs assigned to it in order of their number. The cost of the schedule µ is the sum of weighted completion times, i.e.,

Γ (µ) = k∈J j∈J:j≤k, µ(j)=µ(k) p j • w k . ( 1
)
The objective is to minimize the cost of the schedule. We denote by opt the optimal cost, by σ µ : J → N the function that maps every job to its completion time under µ and by ≺ a partial order on J such that j ≺ k if and only if j < k and s j ≤ s k . Note that we explicitly disallow p j = 0. This is for convenience, and ensures that the Smith ratio w j /p j is always well defined. Our results easily extend to the case where jobs with zero processing time are allowed.

The problem of minimizing the sum of weighted completion times without ordering constraints is a classic problem that has long been known to be strongly NP-hard [START_REF] Garey | Computers and Intractability. A Guide to the Theory of NP-Completeness[END_REF]. This result extends to fixed-order scheduling as well: given an assignment of jobs to a machine, it is always optimal to schedule them in decreasing order of Smith ratio, so the ordering constraints become redundant if

s 1 ≥ s 2 ≥ • • • ≥ s n .

Structural properties of optimal solutions

In this section we will provide a characterization of an optimal solution which will help us construct a constant-factor approximation algorithm in Section 4.

Unit processing times

Suppose all jobs have equal processing time and hence that the relation j ≺ k indicates that j < k and w j ≤ w k . W.l.o.g. we may then as well assume that the processing times are 1. An initial simplification is that we will assume that schedules are staircase shaped, in the sense that for every prefix of the jobs 1, . . . , k, the number of jobs assigned to each machine decreases monotonically with the machine index. We will use the following equivalent definition.

Definition 1. A schedule µ is staircase shaped if for each job k, µ(k) = |{j < k : σ µ (j) = σ µ (k)}| + 1.
Given any schedule µ, we can clearly turn it into a staircase shaped schedule without changing the completion time of any job.

Clearly we want jobs with high weights to be completed early, but this may not always be possible because of the ordering on the jobs. Intuitively, it seems like a good idea to 'reserve' some of the good spots early in the schedule, for higher weight jobs later in the sequence. In staircase shaped schedules this means that early and low weight jobs should be put on low index machines as much as possible. Lemma 1 below makes this more precise.

Definition 2. A schedule µ is Smith-monotone if, for every j ≺ k, it holds that µ(j) ≤ µ(k).
Lemma 1. For unit processing times, there exists an optimal schedule that is Smith-monotone and staircase shaped.

Proof. Let us define the potential function j∈J µ(j)j. Let µ be a solution maximizing this potential function among those that are optimal and staircase shaped. Suppose µ is not Smith-monotone. We obtain a contradiction by showing there is a staircase shaped schedule with a higher potential but no higher cost.

Since µ is not Smith-monotone, there exists a pair j ≺ k that violates Smith monotonicity. Pick j, k so that there is no other violating pair j ≺ k between it, i.e with j ≤ j and k ≤ k and at least one of the inequalities strict. We call such a pair tight. For g = j, k, let S g = {h ∈ {j + 1, . . . , k -1} : µ(h) = µ(g)} be the set of jobs between j and k on the machine of job g. It follows that h ∈ S k =⇒ w h ≤ w j and that h ∈ S j =⇒ w h ≥ w k as, otherwise, the pair j ≺ k would not be tight. (In fact, < holds.) By assigning j to the machine of k and vice-versa we get a schedule µ that improves our potential function. We first show is that the new schedule µ does not incur a higher cost than µ.

Since only the starting times (whence completion times) of j, k and jobs in S j and S k may change, all others remaining equal, it follows that

h∈{j}∪S k σ µ (h) + h∈{k}∪Sj σ µ (h) = h∈{j}∪S k σ µ (h) + h∈{k}∪Sj σ µ (h), hence h∈{j}∪S k (σ µ (h) -σ µ (h)) = h∈{k}∪Sj (σ µ (h) -σ µ (h)).
(

) 2
Now note that the completion times of jobs j and S k increase, while those of k and S j decrease, since the schedule was staircase shaped. Combining this with the fact that w h ≤ w j for h ∈ S k and w h ≥ w k for h ∈ S j , we can bound the increase in the cost as follows:

h∈{j,k}∪Sj ∪S k w h (σ µ (h) -σ µ (h)) = h∈{j}∪S k w h (σ µ (h) -σ µ (h)) - h∈{k}∪Sj w h (σ µ (h) -σ µ (h)) ≤ w j h∈{j}∪S k (σ µ (h) -σ µ (h)) -w k h∈{k}∪Sj (σ µ (h) -σ µ (h)) ≤ 0 by (2).
So the new schedule has a higher potential function and no higher cost. The schedule may not be staircase shaped, however. But simply sorting the jobs fixes this without undoing our work. To see this, note that the set of timeslots occupied on each machine did not change when we modified the schedule. So the fact that the old schedule was staircase shaped, implies that the new schedule still has the following weaker property: if exactly k jobs are scheduled at time t, they are scheduled on the first k machines. By sorting all the jobs assigned to one timeslot by number and assigning them to the first available machine in that order, the potential function can only increase further, while completion times stay the same. Hence, we have found an optimal staircase shaped schedule with higher potential function than we started with, contradicting our choice of the original schedule and concluding the proof.

General processing times

Unfortunately, for general processing times we cannot hope for an equally nice structural result. Indeed, there may not be an optimal schedule that is Smithmonotone. However, as we will now show, we may impose this structure with the loss of only a constant factor in the objective.

The proof works by reducing a general instance to one with unit processing times, finding an optimal Smith-monotone schedule, and then rounding it back. Although this reduction is not polynomial time, it will suffice to prove the bound on the optimality ratio. Instead, in the next section we will find that we can bypass the reduction, and approximate such a schedule directly.

Given an instance I to the general problem, let I unit be the instance with unit processing times obtained from I by replacing every job j ∈ J with a set U (j) = {j 1 , . . . , j pj } of p j consecutive jobs, each having unit processing time and weight w j /p j . Let J unit be the set of jobs of I unit and opt unit be the optimal cost for I unit . Lemma 2. opt unit ≤ opt -j∈J 1 2 (p j -1)w j Proof. The statement follows for the schedule µ unit obtained from the optimal schedule for I by putting all the jobs in U (j) on the machine µ(j), for all j ∈ J.

The completion times of the jobs in U (j) run from σ(j) -p j + 1 to σ(j), and hence the average completion time is σ(j) -1 2 (p j -1). The proof follows from multiplying by the total weight of the jobs in U (j). Lemma 3. An optimal Smith-monotone schedule for I has cost at most opt unit + j∈J (p j -1)w j .

Proof. Given an optimal schedule µ unit for I unit , we can create a schedule for I by putting job j on machine i with probability |{h ∈ U (j) : µ unit (h) = i}|/|U (j)|, for all j ∈ J. The expected time spent processing job j ∈ J on machine i is exactly |{h ∈ U (j) : µ unit (h) = i}|. As a consequence, the expected starting time of a job j ∈ J is at most the average starting time of the jobs in U (j), and thus the expected completion time is at most the expected completion time of jobs in U (j) plus p j -1 (which is the difference between the processing time of job j and any job in U (j)).

What remains to show is that µ is Smith-monotone. By Lemma 1 we can assume, w.l.o.g., that the optimal solution of I unit satisfies Smith monotonicity. Consider an arbitrary pair j ≺ k. We have that j ≺ k for all jobs j ∈ U (j), k ∈ U (k). This implies that, if any job in U (j) is scheduled on machine i, all jobs in U (k) are scheduled on machines with index not smaller than i. Hence it holds that the machine with highest index to which j may be assigned cannot have index larger than any machine to which k may be assigned. Therefore, for every possible realization of the random schedule, Smith monotonicity is satisfied, completing the proof. Lemma 4. An optimal Smith-monotone schedule has cost at most 3 2 opt.

Proof. By Lemma 3, we have that an optimal Smith-monotone schedule has cost at most opt unit + j∈J (p j -1)w j , which in turn, by Lemma 2, is at most

opt + 1 2 j∈J (p j -1)w j ≤ 3 2 opt.
Though the bound in Lemma 4 is unlikely to be tight, it cannot be improved much further. The Kawaguchi-Kyan bound of 1+ √ 2 2 ≈ 1.207 is known to be tight [START_REF] Kawaguchi | Worst case bound of an LRF schedule for the mean weighted flow-time problem[END_REF][START_REF] Schwiegelshohn | An alternative proof of the Kawaguchi-Kyan bound for the Largest-Ratio-First rule[END_REF], and this lower bound carries over to fixed-order scheduling: the worst-case example uses jobs with equal Smith ratios, and in that case reordering the jobs assigned to a machine does not change the cost.

A constant factor approximation algorithm

In this section we will describe an algorithm that proves our main result: Theorem 1. Our approach is as follows: first we round the instance such that all Smith ratios are powers of 1 3 (by rounding up the weights as appropriate). Given that, we show that a certain relaxed objective function is always within a constant of the original objective function. We then use LP rounding to find a Smith-monotone schedule that is optimal with respect to the relaxed objective function.

Theorem 1. Fixed-order scheduling can be approximated to within a factor From hereon assume that all Smith ratios are powers of some fixed γ ∈ (0, 1). Suppose we relax the objective function [START_REF] Allahverdi | The third comprehensive survey on scheduling problems with setup times/costs[END_REF] to disregard the contribution of processing times of jobs with j < k and w j > w k (hence, j ≺ k) in the completion time of job k. We claim this relaxation loses only a factor ( 41-

√ γ -3). Definition 3. The partial completion time of a job k ∈ J under a schedule µ is ck = j k:µ(j)=µ(k) p j .
The partial cost of a schedule µ is Γ (µ) = k∈J w k ck .

It is crucial that the Smith ratios are powers of γ; this ensures that either j k or w j is relatively large compared to w k . Intuitively, in the latter case we don't care too much about the effect of j's processing time on the lighter-weight job k.

Theorem 2. Take an instance where all Smith ratios are positive powers of γ ∈ (0, 1). Consider any schedule µ and denote its cost by Γ (µ). It holds that

Γ (µ) ≤ Γ (µ) ≤ 4 1 - √ γ -3 • Γ (µ).
Since it is obvious that Γ (µ) ≤ Γ (µ) we prove the upper bound.

To simplify notation assume the instance has only one machine; the result can be applied to each machine individually. For d ∈ N, let N d be the set of jobs j with s j = γ d ; let W d and P d be, respectively, the total weight and total processing time of jobs in N d . We denote by

H d = 1 W d k∈N d w k ck the weighted average of the partial cost in N d . It follows that Γ (µ) = k∈J w k ck = d∈N W d H d = d∈N γ d P d H d . (3)
Our goal is to bound Γ (µ) in the same terms. Since H d only accounts for the contribution of jobs with Smith ratio at most γ d in the completion time of jobs in N d , we need to correct for the other jobs (that are in N 1 , . . . , N d-1 ). In the worst case, all these jobs are scheduled first and hence their processing times need to be added. Therefore we get:

Γ (µ) ≤ d∈N W d (H d + d-1 i=1 P i ) ≤ d∈N γ d P d (H d + d-1 i=1 P i ). (4)
We will prove that this value can be bounded by the desired constant times Γ (µ). Globally our strategy is to show that every newly introduced term γ d P d P i can be charged to a term in the expression for Γ (µ) such that no term gets charged more than a 4 1-√ γ -4 fraction of its value.

Before we can proceed we will need the inequality in Lemma 5 below. It says that the average weighted completion time in N d is at least half the total processing time in N d , which can intuitively be seen as follows: think of all jobs j ∈ N d as blocks of equal width, length p j and mass w j . So, all blocks have equal density. Now stack the boxes on top of each other: then P d corresponds to the total length, and H d approximately to the center of mass, which is in the middle.

Lemma 5. P d ≤ 2H d .
Proof.

H d = 1 W d k∈N d w k j≤k∧sj ≤s k p j ≥ 1 W d k∈N d w k j≤k∧j∈N d p j :=Q Suppose now that Q < P d 2 . Since W d = γ d P d , it follows that: Q = 1 P d k∈N d p k (P d - h>k∧h∈N d p h ) = P d - 1 P d h∈N d p h k<h∧k∈N d p k ≥ P d -Q, implying that Q ≥ P d /2, a contradiction. Lemma 6. max{γ d P d H d , γ i P i H i } ≥ 1 2 (γ d P d P i )γ 1 2 (i-d) .
Proof. Suppose that

γ d P d H d < 1 2 γ d P d P i γ 1 2 (i-d)
. This implies that

H d < 1 2 P i γ 1 2 (i-d) . (5)
So we obtain

γ d P d P i γ 1 2 (i-d) ≤ γ d 2H d P i γ 1 2 (i-d) (5)
< γ d-i γ i P i γ

1 2 (i-d) P i γ 1 2 (i-d) ≤ 2γ i H i P i ,
where the first and third inequalities follow from Lemma 5.

We are now ready to prove Theorem 2.

Proof (Theorem 2). We will prove the following inequality, implying the theorem by (4):

d∈N γ d P d H d 4 1 - √ γ -4 ≥ d∈N γ d P d d-1 i=1 P i .
Applying Lemma 6 and replacing the max by a sum we get:

d∈N γ d P d d-1 i=1 P i ≤ d∈N d-1 i=1 γ 1 2 (d-i) 2 max(γ d P d H d , γ i P i H i ) ≤ d∈N d-1 i=1 γ 1 2 (d-i) 2(γ d P d H d + γ i P i H i ) ≤ d∈N ∞ i=1 γ 1 2 i 4(γ d P d H d ) = d∈N γ d P d H d ( 4 1 - √ γ -4).

Linear Programming Relaxation

Suppose all Smith ratios are positive powers of γ ∈ (0, 1). The following mixedinteger program captures the problem of finding a Smith-monotone ordering that minimizes the modified objective Γ (µ).

min k∈J w k ck s.t. u k ≥ u j + z jk ∀j ≺ k (6)
u k ≤ m ∀k ∈ J (7) ck ≥ p k + j≺k (1 -z jk )p j ∀k ∈ J (8)
u k ∈ N, z jk ∈ {0, 1} ∀k ∈ J, j ≺ k
Here, z jk is the indicator variable for the event that j and k are assigned to different machines. The variable u k indicates which machine job k is assigned to. Finally, ck represents the partial completion time of job k. The constraint ( 6) is valid since we require a Smith-monotone ordering. Now consider the natural LP relaxation of this mixed-integer program, where we drop the integrality requirements and instead require 1 ≤ u k ≤ m, 0 ≤ z jk ≤ 1. Denote this relaxation by (LP). Let (z * , u * , c * ) be an optimal solution to (LP), with cost opt lp . Definition 4. For β ∈ (0, 1), the β-point schedule associated to u * is the schedule obtained by assigning job j to machine u * j -β . From now on, β will be chosen uniformly at random from (0, 1), making the β-point schedule a random schedule.

Let N d be the set of jobs with Smith ratios γ d and let Ck be the (random) partial completion time of job k under the β-point schedule. The following statements are easy to verify. Proposition 1. For any pair of jobs j ≺ k, the probability that jobs j and k are assigned to the same machine under the β-point schedule is at most 1 -z * jk . Proof. This follows immediately from the constraint (6).

Proposition 2. For any

k ∈ J, E[ Ck ] ≤ c * k . Hence E k∈J w k Ck ≤ k∈J w k c * k = opt lp .
Proof. This follows from Proposition 1 and (8).

Note that a β-point schedule can be derandomized in polynomial time: a job j is always assigned to u * j when u * j is integral and to either u * j or u * j otherwise. Let b j be the maximum value of β for which u * j -β = u * j . It follows that all possible schedules are the ones obtained by assigning to β the values in {b j |j ∈ J} ∪ {1}.

Constant factor approximation

We are now ready to complete the main proof of this section.

Proof (Theorem 1). Given an instance I where the jobs have arbitrary Smith ratios, let I γ be the instance obtained from I by rounding up the weights such that the Smith ratios are powers of γ, where γ will be defined later, and then scaled to be in (0, 1). Let opt I and opt I γ be the the optimal cost for the instances I and I γ respectively. Clearly the cost of any schedule µ on I γ is at most γ -1 times the cost of µ on I and opt I ≤ opt I γ since the cost of a schedule is linear in the weights (see ( 1)) and weights do not affect feasibility.

We denote by µ and opt lp , respectively, the β-point schedule and the optimal cost of (LP) on I γ . By Lemma 4, Proposition 2 and Theorem 2, the cost of µ on I is at most

3 2 4 1 - √ γ -3 •opt lp ≤ 3 2 4 1 - √ γ -3 •opt I γ ≤ 3 2 4 1 - √ γ -3 •opt I γ -1 .
Minimizing over γ, this yields an approximation ratio of min γ∈(0,1)

3 2 4 1 - √ γ -3 • γ -1 = 3 2 (9 + 6 √ 3) = 27 2 + 9 √ 3
when γ = 1/3, concluding the proof.

Epilogue

Our work suggests many further interesting and natural directions. One is to find a PTAS (or even a polynomial time exact algorithm) for unit processing times, perhaps expanding on the QPTAS in the appendix. Good approximation algorithms for all of the following problems remain open questions.

(1) There are k arrival lines that need to be dispatched over m servers, such that the FIFO ordering in each of the arrival lines is obeyed in each of the server queues. (2) An arbitrary partial order on the jobs is given, and we require that if two jobs are assigned to the same machine, then the partial order is respected.

(1) is exactly this problem, where the partial order is described by k disjoint chains.

(3) Instead of requiring that the order is exactly preserved, a natural relaxation is to allow a reordering buffer (see, e.g. [START_REF] Räcke | Online scheduling for sorting buffers[END_REF]) of limited size. Jobs enter the buffer in the given FIFO order, but any job in the buffer can be chosen and assigned to one of the machines.

σ µ (k) > σ µ (j), since µ is staircase shaped, so it must be that j and k are both in the same segment (R i , R i+1 ] for some i. So we can simply swap k and j to obtain a lexicographically smaller schedule of the same rounded objective value.

For segmented staircase schedules, we can compactly describe the loads on the machines just prior to assigning job j. Let X j i be the number of jobs on machines with load currently in the interval [R i , R i+1 ) just prior to assigning job j. Since only one of the machines with load in that interval can have strictly more than R i jobs on it, this number also completely determines how many machines there are with loads exactly R i . For each j, we have n O(log 1+ n) options for the values of X j 1 , X j 2 , . . . , X j s . Once we know the minimum cost of a schedule attaining each of those options, we can compute the cost of all the schedules up to job j + 1. Hence, we get the main result of this section. Theorem 3. For any > 0, there is a (1 + )-approximation algorithm for fixed-order scheduling with unit processing times with running time n O(log 1+ n) .

27 2 + 9 √ 3 <

 293 29.1 .

This work was partially supported by the Netherlands Organisation for Scientific Research (NWO) through a VIDI grant (016.Vidi.189.087) and the Gravitation Programme Networks (024.002.003).

A A QPTAS for unit processing times

In this section we sketch a simple quasipolynomial time approximation scheme (QPTAS) for the problem under unit processing times. Note that we do not know if this version of the problem remains NP-hard. However, it seems to capture most of the difficulty, so we feel that tackling this case will help substantially in improving the upper bound for the general case. The QPTAS works by solving a relaxed problem by dynamic programming. We round the completion times to geometric intervals and then we consider schedules in which at any time point only one machine per completion time can accept jobs. This sufficiently reduces the solution space to get a quasipolynomial time algorithm.

The first step is to consider only a logarithmic number of distinct completion times. Let R = { (1 + ) i : i ∈ N} be the set of integers found by rounding down a geometric series growing with rate 1 + . Then order the elements 1 = R 1 < R 2 < . . . and take R 0 = 0 by convention. Assume that s is the smallest index such that R s ≥ n, and note that s = O(log 1+ (n)). Now consider the objective of minimizing the weighted sum of rounded completion times, where each completion time is rounded up to the nearest R i . Call this the rounded objective; clearly the rounded objective of any schedule is at most 1 + times the actual objective. So, if we can find an optimal segmented schedule for the rounded objective, we immediately get a (1 + )-approximation to the original problem.

Now we define a restricted type of schedule, which we call a segmented staircase schedule. A segmented staircase schedule is similar to a staircase shaped schedule, except that the "steps" are now defined in terms of the rounded completion times. When j is assigned to a machine, it is assigned to the leftmost machine that gives it the same rounded completion time. In other words, if a job j gets assigned to µ(j) and gets completed at time t ∈ (R i , R i+1 ], then µ(j) is the lowest index machine for which the number of jobs k < j assigned to it does not exceed R i+1 -1.

Lemma 7.

There is an optimal solution to the problem of minimizing the rounded objective that is a segmented staircase schedule.

Proof. Take µ to be a schedule for which (µ(1), µ(2), . . . , µ(n)) is lexicographically minimal amongst all solutions that are optimal for the rounded objective. Notice that µ must be staircase shaped; otherwise, transforming it into a staircase shaped schedule would yield a schedule µ in which every job has the same completion time, but which is lexicographically smaller than µ.

Suppose for a contradiction that this schedule is not a segmented staircase schedule. Let j be the last (maximum index) job that violates the rule for a segmented staircase schedule: j is assigned to machine h , but h < h is the smallest index machine that gives it the same rounded completion time, ignoring all jobs after j. Let k be the first job k > j scheduled on machine h. (If there is no such job, then moving j to h reduces the lexicographical value and does not increase the total rounded completion time.) Note that since j was chosen maximally, no job with j < < k is scheduled on machine h . Moreover,


Mai Alzamel
email: [mai.alzamel@kcl.ac.uk

Alessio Conte

Daniele Greco
email: grc.daniele.cs@gmail.com

Veronica Guerrini

Costas Iliopoulos
email: costas.iliopoulos]@kcl.ac.uk

Nadia Pisanti

Nicola Prezza
email: nicola.prezza]@di.unipi.it

Giulia Punzi
email: giuliagpunzi@gmail.com

Giovanna Rosone
email: giovanna.rosone@unipi.it

Online Algorithms on Antipowers and Antiperiods

Keywords: antiperiod, antipower, power, periodicity, repetition, regularities, online algorithms

The definition of antipower introduced by Fici et al. (ICALP 2016) captures the notion of being the opposite of a power : a sequence of k pairwise distinct blocks of the same length. Recently, Alamro et al. (CPM 2019) defined a string to have an antiperiod if it is a prefix of an antipower, and gave complexity bounds for the offline computation of the minimum antiperiod and all the antiperiods of a word. In this paper, we address the same problems in the online setting. Our solutions rely on new arrays that compactly and incrementally store antiperiods and antipowers as the word grows, obtaining in the process this information for all the word's prefixes. We show how to compute those arrays online in O(n log n) space, O(n log n) time, and o(n ) delay per character, for any constant > 0. Running times are worst-case and hold with high probability. We also discuss more space-efficient solutions returning the correct result with high probability, and small data structures to support random access to those arrays.

Introduction

String properties that highlight regularities such as periodicity, powers, repetitions, palindromes, as well as properties that-dually-highlight diversity (e.g. being square-free, non-periodic, etc.), have been extensively investigated in literature. They have been studied both in terms of combinatorial properties [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] and of algorithmic methods to detect or certify them in a single string [START_REF] Crochemore | Jewels of stringology[END_REF][START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF], or finding maximal common factors that share such properties [START_REF] Chowdhury | Computing a longest common palindromic subsequence[END_REF][START_REF] Bae | On finding a longest common palindromic subsequence[END_REF][START_REF] Inenaga | A hardness result and new algorithm for the longest common palindromic subsequence problem[END_REF][START_REF] Inoue | Computing longest common square subsequences[END_REF][START_REF] Ayad | Longest property-preserved common factor[END_REF][START_REF] Alzamel | Quasi-Linear-Time Algorithm for Longest Common Circular Factor[END_REF]. In addition to having a combinatorial interest on their own, such string properties are also very relevant for several applications [START_REF] Lothaire | Applied Combinatorics on Words. Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Lothaire | Review of applied combinatorics on words[END_REF][START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF]. For instance, they are at the core of many problems arising in biological sequence analysis [START_REF] Li | Pseudo-periodic partitions of biological sequences[END_REF][START_REF] Kolpakov | mreps: efficient and flexible detection of tandem repeats in DNA[END_REF].

Arguably, one of the most natural notions of regularity is that of an exact repetition (power), i.e. a substring consisting of two or more consecutive identical factors. The number of these factors, or blocks, is called the order of the repetition. The study of powers began in the early 1900s with the work of Thue [START_REF] Thue | Uber unendliche zeichenreihen[END_REF], who studied a class of strings that do not contain any substrings that are powers. Recently, a new notion of string diversity in terms of powers has been introduced: an antipower of order k (k-antipower) is a string that can be decomposed into k pairwise-distinct blocks of identical length [START_REF] Fici | Anti-Powers in Infinite Words[END_REF][START_REF] Fici | Anti-powers in infinite words[END_REF]. An antipower is the opposite of a power; i.e., a concatenation of blocks that have the same length but are all different. 4 Likewise, the concept of antiperiod is symmetrical to that of period: an integer p is a period for a word w if and only if w is a prefix of a power with blocks of length p, whereas is an antiperiod for w if and only if it is a prefix of an antipower with blocks of length [START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF].

With respect to infinite words, in [START_REF] Fici | Anti-Powers in Infinite Words[END_REF] the authors prove that regardless of the alphabet size, every infinite word must contain powers of any order or antipowers of any order; i.e., the existence of powers or antipowers is an unavoidable regularity (cf. also [START_REF] Fici | Anti-powers in infinite words[END_REF]). Inspired by this seminal work, Defant [START_REF] Defant | Anti-power prefixes of the Thue-Morse word[END_REF] studied the sequence of lengths of the shortest prefixes of the Thue-Morse word that are kantipowers, and proved that this grows linearly in k. The latter result is further extended in [START_REF] Burcroff | k,λ)-anti-powers and other patterns in words[END_REF] to a generalization of k-antipowers defined in [START_REF] Fici | Anti-powers in infinite words[END_REF].

For finite words, the first algorithmic approach concerning antipowers appeared in [START_REF] Badkobeh | Algorithms for anti-powers in strings[END_REF]. In this work, the authors tackle the problem of finding all the factors of a string w that are k-antipowers. Specifically, they prove that the number of such factors over an alphabet of any size is Ω(n 2 /k), and provide an algorithm that finds them all in O(n 2 /k) time and linear space. The latter results are improved in [START_REF] Kociumaka | Efficient representation and counting of antipower factors in words[END_REF], where the authors give an algorithm that counts and reports the number C of substrings of a word w of length n that are k-antipowers, in O(nk log k) and O(nk log k + C) time, respectively. Moreover, they are also able to test whether a factor w[i, j] is a k-antipower (i.e, answering an antipower query (i, j, k)) in O(r) time, by constructing a data structure of size O(n 2 /r) in O(n 2 /r) time, for any r ∈ {1, . . . , n}. As far as antiperiods are concerned, Alamro et al. [START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF] are the first to give algorithmic results. Specifically, they compute all antiperiods of a string of length n in O(n log n) time, by employing a split-find data structure with initialization time O(n) and linear space, which quickly answers monotone weighted level ancestor queries over the suffix tree. Furthermore, applying recursion to the same solution, they show how to compute just the smallest antiperiod t in O(n log * t) time.

In this paper, we extend the problems considered in [START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF] to the online setting. We show how to efficiently update all the antiperiods (in particular, the minimum one) of a word upon single character extensions. To achieve this, we introduce the notion of purely antiperiodic array-i.e. the array containing, for each word's prefix w [1, i], the smallest block length such that the prefix is an antipower of order i/ -and the more relaxed notion of antiperiodic array, which allows the last block to have length less than . In addition, we provide the more powerful notion of complete antipower array, containing for each possible block length , the greatest i such that the word's prefix w[1, i] is an antipower of order i/ . The complete antipower array stores, implicitly, all antiperiods of all the word's prefixes, as well as the value i/ itself, that is the maximum order for which a prefix of w is an antipower of period i. We show that these arrays can be computed online in O(n log n) space, O(n log n) time, and o(n ) delay per character, for any constant > 0. We also show that if we allow a small (inversepolynomial) probability of failure, then we can compute online the antiperiodic array in O(n) space, O(n log t) time and O(n log t) delay (all running times are worst-case and hold with high probability). Finally, we describe small data structures supporting fast random access to those three arrays, without the need to explicitly store all of them.

Preliminaries and problem definitions

Let Σ = {c 1 , c 2 , . . . , c σ } be a finite ordered alphabet of size σ with c 1 < c 2 < . . . < c σ . Given a word (or string)

w = w[1]w[2] • • • w[n]
∈ Σ * we denote by |w| its length n. We use to denote the empty word. A factor (or substring) of w is written as

w[i, j] = w[i] • • • w[j] with 1 ≤ i ≤ j ≤ n. A factor of type w[1, j] is called a prefix of w, while a factor of type w[i, n] is called a suffix of w. An integer p ≥ 1 is a period of a word w[1]w[2] • • • w[n] where w[i] ∈ Σ if w[i] = w[i + p] for i = i, . . . , n -p.
The smallest period of w is called the period of w.

A power of order k is a string that is the concatenation of k identical equallength blocks of letters. More formally, given a finite word w, w k denotes the word obtained by concatenating k copies of w. For a power of order k and length n, the integer n/k is a period.

Definition 1 ([14]

). An antipower of order k, or simply a k-antipower, is defined as a concatenation of k consecutive pairwise distinct blocks of the same length.

The length of the pairwise distinct blocks is called antiperiod. The notion of antiperiod to words that are not antipowers has been extended in [START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF]: w has an antiperiod if it is a prefix of some k-antipower w whose antiperiod is . Holding this intuition, we formalize a definition of antiperiodic words as follows:

Definition 2. A word w = u 1 . . . u k is called -antiperiodic if (i) u i = u j , for all i = j; (ii) |u i | = , for all i < k; (iii) |u k | ≤ . The number = n
k is an antiperiod for w.

Note that a k-antipower of length n is n k -antiperiodic. Therefore, we also call it purely n k -antiperiodic. Example 1. The word abbbaa is a 3-antipower, therefore it is also purely 2antiperiodic: the distinct-factors partition ab|bb|aa testifies this. The word ababaab is not 2-antiperiodic, but it is 3-antiperiodic: aba|baa|b.

We now formally define the three arrays that will be the output of our online algorithms. The first two arrays respectively store, for each word's prefix, its minimum antiperiod and its minimum pure antiperiod: antiperiodic array (apd) INPUT: A word w of length n OUTPUT: An array of length n where apd[i] is the smallest such that w[1, i] is -antiperiodic.

Purely antiperiodic array (papd)

INPUT: A word w of length n OUTPUT: An array of length n where papd[i] is the smallest such that w[1, i] is a i -antipower.

We further consider the following question: given i and is the prefix w[1, i] (purely) -antiperiodic? We can answer this question by building our third array, the complete array cap of w:

Complete antipower array (cap)

INPUT: A word w of length n OUTPUT: An array of length n where cap[ ] is the maximum index i such that the prefix w[1, i] is purely -antiperiodic.

Example 2. Let w = abaabaab. The antiperiodic array of w is given by apd = [1, 1, 2, 2, 2, 2, 2, 4], its purely antiperiodic array papd = [1, 1, 3, 2, 5, 2, 7, 4], and its complete antipower array is cap = [START_REF] Alzamel | Quasi-Linear-Time Algorithm for Longest Common Circular Factor[END_REF][START_REF] Bille | Longest common extensions in sublinear space[END_REF][START_REF] Ayad | Longest property-preserved common factor[END_REF][START_REF] Chowdhury | Computing a longest common palindromic subsequence[END_REF][START_REF] Bae | On finding a longest common palindromic subsequence[END_REF][START_REF] Bille | Longest common extensions in sublinear space[END_REF][START_REF] Burcroff | k,λ)-anti-powers and other patterns in words[END_REF][START_REF] Chowdhury | Computing a longest common palindromic subsequence[END_REF].

In the next sections, we show how to build these arrays online, and how to access them using little space (i.e. less space than the three explicit arrays).

Basic Properties of Antiperiodic Words

First, we provide some properties of (purely) -antiperiodic words.

Lemma 1.

If is an antiperiod for some word w of length > , then is also antiperiod for

w = w[1, |w| -1].
Proof. First, let us assume does not divide |w|. By hypothesis, all blocks

u s = w[(s -1) + 1, s ] for s = 1, ..., |w| = k -1 and u k = w[ |w| + 1, |w|] are pairwise distinct. Let u k = u k [1, |u k | -1]
(possibly the empty word); then the blocks u 1 , ..., u k-1 are still distinct, and they are all also distinct from u k since they are of different lengths. Therefore, since w

= w[1, |w| -1] = u 1 • • • u k-1 u k ,
is an antiperiod for w . If divides |w|, the proof still holds with last block being u k-1 instead of u k .

Proposition 1. The following properties hold: i) If a word w is -antiperiodic, then for all i ≥ the prefix w[1, i] isantiperiodic. ii) If a word w is purely -antiperiodic, then for all i ≥ such that divides i,

the prefix w[1, i] is purely -antiperiodic. iii) If a prefix w[1, j] is purely -antiperiodic, then w[1, i] is -antiperiodic for all ≤ i < j + .
Proof. Properties i) and ii) follow by recursively applying Lemma 1. In order to prove Property iii), we assume that w[1, j] is purely -antiperiodic. By part i) we have that the thesis holds for i ∈ [ , j]. On the other hand, if w[1, j] is purelyantiperiodic, then the blocks u s = w[(s -1) + 1, s ] for s = 1, . . . , j are pairwise distinct. Therefore they are also trivially distinct from u h = w[j + 1, h] for all h < j + , since they are of different lengths. This ensures the -antiperiodicity of w[1, i] for j < i < j + .

Algorithmic and data structures toolkits

We make use of Karp-Rabin fingerprinting [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF] in the more modern variant, where the fingerprint is a polynomial modulo a prime number evaluated at a random point. To make the paper self-contained, we recapitulate these notions.

Definition 3 (Karp-Rabin fingerprinting [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF]). The Karp-Rabin hash function (over integer alphabet) is defined as

h q,x (w) = |w| i=1 w[i] • x |w|-i mod q,
where q is a prime and x is a random integer in [1, q]. The value h q,x (w) will be called hash value or fingerprint of w interchangeably. In the following, with high probability (or inverse-polynomial probability) means with probability at least 1 -n -c for an arbitrarily large constant c fixed at construction time, where n is the input's size. We will often say that running times of our algorithms hold with high probability. This means that the algorithm terminates in the claimed running time (or has the claimed delay) with probability 1 -n -c for an arbitrarily large constant c fixed at construction time. On the other hand, with probability n -c the algorithm (or single operations) could take polynomial time to terminate.

A crucial property of Karp-Rabin fingerprinting is that, with high probability, no collision occurs among the factors of a given word. To see this, consider two words s = t of length n. The polynomial h q,x (s) -h q,x (t) has at most n roots modulo (prime) q, so the two words collide (i.e. h q,x (s) -h q,x (t) = 0) with probability n/q. For big enough q we take care of all possible O(n 2 ) collisions between the factors of a word of length n: Lemma 2. For a sufficiently large prime q such that log q ∈ Θ(log n), the hash function h q,x is collision-free over all factors of any fixed word w[1, n] with highprobability.

If n is not known in advance (e.g. in the online setting), in the above lemma we can take instead log q ∈ Θ(ω), where ω is the machine word size. We thus work in the word RAM model, where the word size always satisfies ω = Ω(log n) for any input size n and standard arithmetic operations between Θ(ω)-bits numbers take constant time.

In our application we will need to check collisions between factors of the current word in an online fashion, with small delay per added character. The following standard extension of Karp-Rabin fingerprinting (see also [START_REF] Bille | Longest common extensions in sublinear space[END_REF]) will allow us to reach this goal.

Definition 4 (Extended Karp-Rabin fingerprinting). The extended Karp-Rabin hash function is defined as

κ q,x (w) = h q,x (w[1, 2 log 2 |w| ]), h q,x (w[|w| -2 log 2 |w| + 1, |w|]), |w|
We say that κ q,x is collision-free on w if κ q,x does not generate collisions among factors of w. Note that κ q,x is collision-free on w if and only if h q,x is collision-free among the factors of w whose length is a power of two.

A dictionary D is a data structure implementing a set of objects (e.g. integers). Each object x is associated with some satellite information y (e.g. another integer), which is retrieved using the notation y ← D[x]. A dynamic dictionary supports the insertion of pairs (object, satellite information) x, y as D[x] ← y.

In our algorithms we will use the dictionary design of Dietzfelbinger et al. [START_REF] Dietzfelbinger | A new universal class of hash functions and dynamic hashing in real time[END_REF]: Lemma 3 (Dynamic Dictionaries [START_REF] Dietzfelbinger | A new universal class of hash functions and dynamic hashing in real time[END_REF]). There exists a linear-space dynamic dictionary data structure supporting insertion and retrieval operations in constant worst-case time w.h.p.

The probabilities involved in the performance of our algorithms will depend solely on the random choices they make (e.g. choosing the hash function), not on the input word w (which may be arbitrary). However, we do require that the word w is fixed before the algorithm starts, i.e. before the random choices are made. This is a standard assumption with randomized dynamic data structures; violating this assumption is equivalent to using fully-deterministic structures, for which strong lower-bounds apply (see, e.g., the case of dictionaries considered by Dietzfelbinger et al. [START_REF] Dietzfelbinger | Dynamic perfect hashing: Upper and lower bounds[END_REF], who also make the same assumption).

Online algorithms

In this section, we first discuss how to compute the antiperiodic array apd (by using two different approaches), and then extend the solution to papd and to cap arrays. The final goal of this section will be proving the following theorems: Theorem 1. The antiperiodic array ( apd) of a word w of length n can be computed with an online solution working in O(n) space, O(n log t) time, and O(n log t) delay per character, where t is the smallest antiperiod of w. Running times are worst-case and hold w.h.p. The returned solution is correct w.h.p.

Theorem 2. The antiperiodic array ( apd), purely antiperiodic array (papd) and complete antipower array (cap) of a word w of length n can be computed with an online solution working in O(n log n) space, O(n log n) time, and o(n ) delay per character for any constant > 0. Running times are worst-case and hold w.h.p.

The proof of Theorem 1 is given in Section 3.1 and the proof of Theorem 2 follows immediately from Lemmas 6, 7, and 8.

Whenever we say we use a dictionary or an array, it is assumed we use the data structure of Lemma 3. This way, we do not need to assume that the final size n of the text is known. Note that this dictionary offers stronger guarantees than classic hash tables, where query times are constant only in expectation. Similarly, a simple array can be used to represent a dynamic text with rightappend operations; however, also in this case resizing operations (e.g. doubling techniques) require O(n) delay in the worst case. In order to achieve a small delay in our online algorithms, we cannot afford paying such overheads and thus opt for the structure of Lemma 3.

The following dynamic string data structure stands at the core of our results. It extends standard techniques (see e.g. [START_REF] Bille | Longest common extensions in sublinear space[END_REF]) to the online setting to efficiently compute the extended Karp-Rabin fingerprint of any factor and check collisions among them. Lemma 4. There is a O(n log n)-space data structure on a word w[1, n] that computes κ q,x (w[i, j]) in constant time for any 1 ≤ i ≤ j ≤ n, where κ q,x is collision-free. The structure can be updated in O(log n) time by appending a new character to the end of w, possibly changing function κ q,x if a collision is detected. Space and update time can be reduced to O(n) and O(1), respectively, at the cost of using a hash function that is collision-free with high probability only. In all cases, running times are worst-case and hold w.h.p.

Proof. Similarly to Bille et al. [START_REF] Bille | Longest common extensions in sublinear space[END_REF] (where they consider more space-efficient variants), we store the hash value of every prefix of w. Then, the fingerprint value of any factor can be computed by subtracting (modulo q) the hashes of two prefixes (the hash of the shortest prefix need also to be multiplied by a suitable power of x, so we compute also all powers of x modulo q). To extend the structure for the word w by one character c, it is sufficient to compute the fingerprint of wc. This can be done with one multiplication and one addition (mod q) to combine the fingerprints of w and c. This is already sufficient to obtain the linear-space version of the structure that is correct with high probability and that supports queries and updates in constant time.

To make the structure collision-free, we check collisions of h q,x among factors whose length is a power of 2. This suffices to ensure that κ q,x is collision-free among factors of any length. For each e = 1, . . . , log n we keep a dictionary C e storing all fingerprints of factors of length 2 e . To each such fingerprint X, we associate a position i such that h q,x (w[i, i + 2 e -1]) = X. Assume that the function is collision-free among factors of w whose length is a power of 2. To extend the property to w = wc, for a character c, first we extend the fingerprinting structure as seen above. Then, for e = 1, . . . , log n (in this order) we do as follows. Assume that the suffix of length 2 e-1 of w does not generate collisions, which at the beginning (e = 1) can be checked in constant time by accessing dictionary C 1 and the word. We look for X = h q,x (w [|w |-2 e +1, |w |]) in C e . If it does not occur, then the suffix of w of length 2 e does not generate collisions. We insert X, |w | -2 e + 1 in the dictionary and we proceed with e + 1. Otherwise, let i < |w | -2 e + 1 be the position found in the dictionary such that h q,x (w [i, i + 2 e -1]) = X. Since by assumption h q,x is collision-free among factors of length 2 e-1 , we can check if w[i, i + 2 e -1] = w [|w | -2 e + 1, |w |] in constant time by comparing the collision-free fingerprints of their two halves. If we detect a collision, then we re-build the whole structure with a new random x. This happens with probability at most n -c for an arbitrarily large constant c, so updates take O(log n) time w.h.p.

The optimal dynamic strings of Gawrychowski et al. [START_REF] Gawrychowski | Optimal dynamic strings[END_REF] could also be used to replace the structure of Lemma 4. However, they support factor comparison in O(log n) time5 , whereas Lemma 4 achieves O( 1) time (at the price of being less space-efficient and supporting less powerful queries). This is crucial to obtain the claimed time bounds in our algorithms.

Online antiperiodic array: linear space construction

Our first solution to build the antiperiodic array relies on its monotonicity. Proposition 2. The antiperiodic array apd is non-decreasing; that is, for all

i < |w|, apd[i] ≤ apd[i + 1].
Proof. We know that apd[i + 1] is an antiperiod for w[1, i + 1]. By Lemma 1, apd[i+1] is also an antiperiod for w [1, i]. Since apd[i] is the minimum antiperiod for this word, apd[i] ≤ apd[i + 1] holds.

We now describe a simple online solution for computing array apd that achieves linear space and O(n log t) running time, where t is the smallest antiperiod of the word, proving Theorem 1.

Proof (Theorem 1). Assume we have processed w[1, i] and computed apd[1, i],

with apd[i] = . We keep the dynamic linear-space data structure of Lemma 4 on w (i.e. the version that is correct w.h.p. only). We also keep a dictionary R containing the fingerprints of all blocks of length up to position i. If does not divide i+1, then we write apd[i+1] = and proceed to i+2. Otherwise, w[i, i+1] ends a block of length . We insert the fingerprint of the last block of length in the dictionary R. If the fingerprint is not already in the dictionary, we can write apd[i + 1] = and proceed to i + 2. Otherwise, is not an antiperiod of i + 1. We empty the dictionary R and look for a new antiperiod = + 1, + 2, . . . . Proposition 2 guarantees that only these antiperiods need to be tried, since apd is non-decreasing. To check antiperiod , we insert the fingerprints of all blocks of length in R in O((i + 1)/ ) time. If a duplicate is found, we empty R and proceed to + 1. We stop at the smallest integer that does not generate duplicates in R (and we keep the current elements in R).

Let t be the smallest antiperiod of the whole word w [1, n]. Overall, we spend time O( t =1 n/ ) = O(n log t). Since we keep only one dictionary at a time, the space is O(n). In the worst case, it could be that we are processing a position i ∈ Θ(n) and that we need to check most of the antiperiods smaller than t, so also the delay is Θ(n log t) in the worst case. Moreover, since we do not check collisions between Karp-Rabin fingerprints, the solution is correct with high probability only.

Online antiperiodic array: reducing the delay

In this section we improve the delay of the solution described in the previous section with an algorithm returning always the correct solution (at the cost of increasing space usage and running time).

Our solution will require to compute the divisors of all numbers i = 1, . . . , n. With the next lemma we show how to achieve this goal in an online fashion and constant time per element. Running time is w.h.p. because we assume that n is not known in advance and we use the dictionary of Lemma 3 to implement a dynamic array; otherwise, if n is known one can use a simple array and remove randomization.

Lemma 5. We can list all d(i) divisors of the integers i = 1, . . . , n in O(d(i)) time per integer and O(n log n) total space. The running time is worst-case and holds w.h.p.

Proof. We show how to build a dictionary D such that D[i] is the multi-set of the O(log i) prime divisors of i: if d is the largest integer such that p d divides i and p is prime, D[i] contains d copies of p. D[i] can be implemented as a simple array (to re-size it, we can simply double its current size: since at most O(log i) primes can divide i, D[i] can be re-sized with delay O(log i), which is acceptable for our purposes). At the beginning, we have D[1] = ∅. Given D[i], all divisors of i can be enumerated in constant time per element by multiplying the integers of any subset of D[i] (with backtracking, to avoid repeating the same multiplications). We also return the trivial divisors 1 and i (or just one of them if i = 1).

Suppose we have computed D [1, i]. To proceed to the next position

i + 1, for each p ∈ D[i] we insert p in D[j], where j = ((i/p) + 1) • p is the next multiple of p. If D[i + 1] is empty, then we insert i + 1 in D[i + 1]. It is easy to see that now D[i + 1]
contains all primes that divide i + 1: let p be a prime dividing i + 1. We have two cases. (i) i + 1 = q • p, with q > 1. Then, by definition of our procedure when we processed D[(q-1)•p] we also inserted p in D[(q-1+1)

•p] = D[i+1]. (ii) i + 1 = p. Then, D[i + 1
] is empty when we visit it and our procedure inserts p in D[i + 1]. Now, if a prime p divides i + 1 we can find the largest power p d dividing i + 1 by simply computing the remainder between i + 1 and p e , for e = 1, . . . , d. We insert d -1 further copies of p in D[i + 1]. Note that we compute each D[i] in O(log i) ⊆ O(d(i)) time and delay, and that at any time D contains at most Θ(n) multi-sets of size O(log n) each (when processing position i, the furthest cell of D that we touch is D[2 • i]; this happens precisely when i is prime).

We can now prove the main result of this section regarding the apd: Lemma 6. Theorem 2 holds with respect to the antiperiodic array.

Proof. Assume we have processed w[1, i] and computed apd [1, i]. We keep the O(n log n)-space data structure of Lemma 4 on w (i.e. the version that always returns the correct result and supports O(log n)-time updates).

We build i dictionaries H 1 , . . . , H i , where H stores all the fingerprints κ q,x (w[ • (j -1) + 1, • j]) for j = 1, . . . , i/ . At each time step, note that the dictionaries store overall O(n log n) elements.

We also keep a log-time successor data structure B (e.g. a red-black tree) storing all the values { 1 , . . . , q } ⊆ [1, i] such that j is an antiperiod of w [1, i].

Now, suppose we extend w[1, i] with a character, obtaining w[1, i + 1], and assume that the last computed value in the antiperiodic array is apd[i] = . To update our structures, we perform the following operations:

1. First, we insert i + 1 in B, since i + 1 is a valid antiperiod of w[1, i + 1].

2. Then, we update the dictionary H j for all j that divide i + 1, i.e. such that a block of length j ends at the end of w[1, i + 1]. Each such dictionary H j is updated by inserting X = κ q,x (w[i -j + 2, i + 1]), i.e. the hash of the last block of length j. If X is already in the dictionary, then j cannot be anymore an antiperiod, and we remove it from B. In Lemma 5 we show how to list all d(i + 1) divisors of i + 1 in constant time per item. Any integer x has at most e O(log x/ log log x) = o(x ) divisors, for any constant > 0, so o(n ) will become our delay. Overall, these operations amortize to O(n log n) time (since

n i=1 d(i) = O(n log n)
, where d(i) is the number of divisors of i).

If apd[i]

= does not divide i + 1, then we set apd[i + 1] = . Otherwise, divides i + 1. Then, is the minimum antiperiod of w[1, i + 1] iff ∈ B. If it is, we set apd[i + 1] = . Otherwise, we find the successor of in B and we set apd[i + 1] = . All these operations take O(log n) time.

Purely antiperiodic array

In this section we extend the solution for computing apd of Section 3.2 to the computation of the purely antiperiodic array papd.

Lemma 7. Theorem 2 holds with respect to the purely antiperiodic array.

Proof. We build the dictionaries H 1 , . . . , H i as in the proof of Theorem 6. We mark each dictionary H with a flag (one bit) recording whether is no longer an antiperiod for the current position i. When processing position i + 1, we scan all divisors of i + 1 (using Lemma 5) and (i) opportunely update the flags whenever for some divisor of i + 1, the current prefix w[1, i + 1] is no longer a i+1 -antipower (but the prefix w[1, (i + 1) -] was), and (ii) find the minimum divisor for which w[1, i + 1] is a i+1 -antipower (i.e. the minimum such that H is not marked). This is the value we write in papd[i + 1]. Our time bounds follow since we spend constant time per divisor of i + 1.

Complete antipower array

In this section we show how to build the complete antipower array cap. Recall that cap[ ] stores the maximum index j such that the prefix w[1, j] is purely -antiperiodic. Thus, for any > n/2 , cap[ ] is trivially equal to its index . With an easy adaptation of Theorem 7 we obtain:

Lemma 8. Theorem 2 holds with respect to the complete antipower array.

Proof. We proceed as in the proof of Theorem 7. We keep i dictionaries H , = 1, . . . , i storing the fingerprints of blocks of length up to position i. We also mark each dictionary H with a flag (one bit) recording (when true) whether is no longer an antiperiod for the current position i. Assume we have computed cap [1, i]. When processing position i + 1, we generate all divisors of i + 1 with Lemma 5. Whenever for some divisor of i + 1, the current prefix w[1, i + 1] is no longer a i+1 -antipower (but the prefix w[1, (i + 1) -] was), we set the flag associated with dictionary H . Then, for all divisors of i + 1 such that the flag of H is false we write cap[ ] ← i + 1. Our time and space bounds follow since the number of divisors is always upper-bounded by o(n ) and the sum of the number of divisors of all i = 1, . . . , n is O(n log n).

Relationships between cap, apd and papd

We observe that the array cap stores more information than arrays apd and papd, which only record the minimum for each word's prefix. Moreover, the following lemma shows the relation between the array cap and the property of being -antiperiodic.

Lemma 9. A prefix w[1, i] is -antiperiodic if and only if ≤ i < cap[ ] + .
Proof. If a prefix w[1, i] is -antiperiodic, it must hold that the length i of the prefix is at least . Moreover, by definition of cap, since cap[ ] = x is the rightmost index of w such that w[1, x] is purely -antiperiodic, it also must hold i < x + . Conversely, suppose we have an index i such that ≤ i < x + , where x = cap[ ]. Then the fact that w[1, i] is -antiperiodic follows by the definition of cap and part iii) of Proposition 1.

Here we show how cap can be used to directly obtain or access efficiently the other two structures. Accessing apd from cap. We show that the array cap allows fast random access to apd. Indeed, the entry apd[i] is the minimum length such that the prefix w[1, i] is -antiperiodic. By Lemma 9, the value apd[i] is the smallest such that ≤ i < cap[ ] + . To find such value we need to find the leftmost entry in cap [1, i] such that cap[ ] + is greater than i.

Given cap, we build a constant-time range maximum data structure (RMQ) on the array A = [cap [START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF] + 1, cap[2] + 2, . . . , cap[n] + n], which requires only 2n+o(n) bits and can be built in linear time [START_REF] Fischer | Space-efficient preprocessing schemes for range minimum queries on static arrays[END_REF]. The structure returns, for every range [i, j], the index containing the maximum element in A. Then, accessing apd[i] corresponds to finding the leftmost entry in A that exceeds i. This can be solved in O(log n) time with binary search using the RMQ on A. Obtaining apd from cap. We show that cap may be used to build apd in O(n) time. Since apd[i] = min{ : w[1, i] is -antiperiodic}, by Lemma 9 it holds apd[i] = min{ : ≤ i < cap[ ] + }. We can thus obtain apd by iterating over cap[ ] and each time setting values of apd that have not already been set. More formally, we start from = 1 and set an auxiliary index j = 1. The index j prevents us from writing twice on the same cell. Given , we mark apd[i] = for all indices i in the range [j, cap[ ] + -1]. Then, we update the index j by setting j = cap[ ] + if j < cap[ ] + , and we repeat the procedure for + 1. Note that if cap[ ] + -1 is smaller than j for some , we do nothing apart from increasing . We stop when apd and cap are of the same length.

When we set apd[i] = , is the smallest value such that i < cap[ ] + . The cost is O(n) as each cell of apd is only written once, and each cell of cap only read once, both arrays having length n. Accessing papd from cap. We further note that cap allows random access to papd by performing just o(n ) accesses to cap (for any > 0). Indeed, papd[i] = min{ : w[1, i] is purely -antiperiodic}. Note that i mod must be 0. This means we can find papd[i] by iterating over each divisor x of i and finding the lowest one such that cap[x] ≥ i. As any integer number i ≤ n has o(n ) divisors, the process takes o(n ) accesses to cap.

To obtain o(n ) running time, one needs to list the divisors of the index i ≤ n in constant time per element. One solution could be dividing i by all numbers j ≤ √ i. This solution successfully finds all divisors in O( √ n) time. This can be improved to o(n ) by explicitly factoring i: integer factorization algorithms like Schnorr-Seysen-Lenstra's [START_REF] Lenstra | A rigorous time bound for factoring integers[END_REF] find all factors of i ≤ n in o(n ) expected time. Obtaining papd from cap. Using the above solution to access each cell of papd, running time amortizes to O(n log n), i.e. the sum of the number of divisors of all numbers i ≤ n. In this case, the divisors can be found using Lemma 5.

Final remarks

In this paper, we showed how to efficiently compute in online fashion the antiperiodic array, the purely antiperiodic array, and the complete antipower array.

Moreover, using the complete antipower array, we can answer in constant time the question posed in Section 2: given i and is the prefix w[1, i] (purely) -antiperiodic? Indeed, w[1, i] is purely -antiperiodic if i mod = 0 and i ≤ cap[ ], and -antiperiodic if ≤ i < cap[ ] + .

Note that the definition of -antiperiodic word w = u 1 . . . u k poses no constraint on the last block u k when its length is strictly less than . We may think of extending/restricting the -antiperiodic notion by imposing conditions on this incomplete block, such as u k not being a prefix (or suffix, factor...) of any u i .

We remark that a word may be a power/antipower for different orders, even though in some cases[START_REF] Alamro | Computing the Antiperiod(s) of a String[END_REF] the focus is on the smallest such order.

Using their interface, factor comparisons can be achieved by extracting (splitting) the factors in logarithmic time, then comparing them in constant time (or, alternatively, by navigating their grammar in logarithmic time without performing splits).

Acknowledgements

The authors would like to thank Roberto Grossi for useful conversations on the topic. GR, NPi are partially, and DG, VG, NPr are supported by the project MIUR-SIR CMACBioSeq ("Combinatorial methods for analysis and compression of biological sequences") grant n. RBSI146R5L.