Narrow Results

We investigate an online scheduling problem on a bounded batch machine with $f$ incompatible job families, in which the jobs are released over time and the jobs belonging to the same family have the same processing times. The goal is to minimize the maximum completion time. A machine can process at most $b$ jobs simultaneously as a batch, where $b$ is finite. A batch only contains the jobs from the same family. KRT setting means that no job is released when the machine is busy. In this paper, we consider the above model under two environments: (1) KRT setting and (2) general setting. In the KRT setting, we provide the lower bounds $1+\frac{\sqrt{f^2-f+1}-1}{f}$ for $b\ge f$ and $min\left\{\frac{2f+1}{f+2},\frac{2b}{b+1}\right\}$ for $2\le b<f$. In the general setting, we provide the lower bounds $1+\frac{\sqrt{4f^2+1}-1}{2f}$ for $b\ge f+1$ and $\frac{2b}{b+1}$ for $2\le b<f+1$. We further present an online algorithm, which is the best possible when $b\ge f$ for the KRT setting and when $b\ge f+1$ for the general setting.

The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets in O(n log n) time, where n is the ending position of the first square. We also note that the same technique yields an O(n·(|Σ_n|+log n))-time algorithm for general alphabets, where |Σ_n| is the number of different symbols in the first n positions of the input string. (This is faster than the previously fastest method for general alphabets when |Σ_n| = o(log² n).) Finally, we present a simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string is still squarefree.

We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.

This work investigates an online two stage k-search problem where an online player makes selections in two stages. In the first stage a number of more than k quoted prices are selected as candidates, and then exactly k highest quoted prices are chosen from the candidates in the second stage. The objective is to maximize the total profit of the k final accepted prices. We mainly propose a deterministic online algorithm and prove that it is optimal in competitiveness. A further discussion is given considering various relationships between the value of k and the number of candidates.

In the online minimum spanning tree problem, a graph is revealed vertex by vertex; together with every vertex, all edges to vertices that are already known are given, and an online algorithm must irrevocably choose a subset of them as a part of its solution. The advice complexity of an online problem is a means to quantify the information that needs to be extracted from the input to achieve good results. For a graph of size $n$, we show an asymptotically tight bound of $\mathrm{\Theta }(nlogn)$ on the number of advice bits to produce an optimal solution for any given graph. For particular graph classes, e.g., with bounded degree or a restricted edge weight function, we prove that the upper bound can be drastically reduced; e.g., $5(n-1)$ advice bits allow to compute an optimal result if the weight function equals the Euclidean distance; if the graph is complete and has two different edge weights, even a logarithmic number suffices. Some of these results make use of the optimality of Kruskal’s algorithm for the offline setting. We also study the trade-off between the number of advice bits and the achievable competitive ratio. To this end, we perform a reduction from another online problem to obtain a linear lower bound on the advice complexity for any near-optimal solution. Using our results finally allows us to give a lower bound on the expected competitive ratio of any randomized online algorithm for the problem, even on graphs with three different edge weights.

The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set $V$ of vertices, construction costs for all possible edges between pairs of vertices from $V$, and a sequence $S_1,S_2,\dots ,S_r\subseteq V$ of connectivity constraints, the objective is to find a set $E$ of edges such that each $S_i$ induces a connected subgraph of the graph $(V,E)$ and the total cost of $E$ is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an $O(B^{2}logn)$-competitive and $O((B+logr)logn)$-competitive polynomial-time algorithms, where $B$ is an upper bound on the size of constraints, while $r,n$ denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an $\mathrm{\Omega }(B)$-competitive lower bound as well as an $\mathrm{\Omega }(\sqrt{B})$-competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an $O(\sqrt{n}(logn+logr))$-competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most $d$. Among other things, we provide a polynomial-time $(\left(\genfrac{}{}{0.0pt}{}{B}{2}\right)-B+2)\left(\genfrac{}{}{0.0pt}{}{B}{2}\right)$-approximation algorithm for the Network Construction problem with the $d$-diameter requirements, when each constraint has at most $B$ vertices, and show the APX-completeness of this variant.

With a rapidly growing attention on the development of learning-augmented algorithms, we revisit the classical online traveling salesman problem (OLTSP) from the perspective of such learning approaches. A learning-augmented online algorithm, or simply an online algorithm with predictions, considers how to improve its competitive performance with theoretical guarantees by forecasting the information of future requests, e.g., their release time or locations in the OLTSP. In this study, we investigate the OLTSP on the real line, motivated by the parcel picking problem in a smart warehouse, which aims at scheduling a route for a server (saying, a Kiva robot), starting at the origin, serving all online requests and returning to the origin such that the completion time is minimized. Each online request is released over time on the real line and the server moves back and forth along the line with unit speed.

We mainly focus on zealous algorithms, a special type of online algorithms for the OLTSP which never allow the sever to wait if there are still unserved requests, and exploit a specific forecasting strategy, called online predictions, which makes a sequence of predictions one by one in an online manner. In order to ensure better competitive performance, we particularly explore the worst-case scenarios that restrict the power of such predictions. Based on the discussion, we make an assumption in which online predictions are guaranteed to be useful, and devise a learning-augmented algorithm with $max\left\{\right.\frac{6\lambda +1}{4\lambda },\frac{2\lambda +1}{2\lambda }\left\}\right.$-robustness and $max\left\{\right.\frac{3}{2}+\frac{{\eta }_t+{\eta }_p}{OPT},\frac{6+\lambda }{4}+\frac{(1-\lambda ){\eta }_p}{OPT}\left\}\right.$-consistency, $0<\lambda \le 1$, comparing to the previous lower bound of $\frac{7}{4}$, where ${\eta }_t$ and ${\eta }_p$ which indicate prediction errors are sufficiently small constants. Moreover, we also conduct numerical experiments to demonstrate the practical effectiveness of the proposed algorithm.

In an online problem, the input is revealed one piece at a time. In every time step, the online algorithm has to produce a part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to nonoptimal solutions. The impact of the partial knowledge depends strongly on the problem. If the algorithm is allowed to read binary information about the future, the amount of bits read that allow the algorithm to solve the problem optimally is the so-called advice complexity. The quality of an online algorithm is measured by its competitive ratio, which compares its performance to that of an optimal offline algorithm.

In this paper we study online bipartite matchings focusing on the particular case of bipartite matchings in regular graphs. We give tight upper and lower bounds on the competitive ratio of the online deterministic bipartite matching problem. The competitive ratio turns out to be asymptotically equal to the known randomized competitive ratio. Afterwards, we present an upper and lower bound for the advice complexity of the online deterministic bipartite matching problem.

With the popularization of energy conservation and emission reduction, amounts of industrial production has taken energy conservation as a goal to achieve. The paper considers an online parallel-batch scheduling problem with deteriorating and incompatible families on identical machines to minimize the makespan, which minimizes the maximum energy consumption of machines. Specifically, the processing time of job $J_j$ is defined by an increasing function of its starting time $t$, i.e., $p_j={\alpha }_j(A+Bt)$, where ${\alpha }_j>0$ is the deterioration rate of job $J_j$. For the problem, we propose an online algorithm with a competitive ratio of $2+B{\alpha }_{max}$, where ${\alpha }_{max}$ is the largest deterioration rate in an instance. Furthermore, the paper presents a concise computational study of the numerical experiment to show that our algorithm performs very well in practice of this model.

In this paper, we consider a variant of the classical parallel machine scheduling problem. For this problem, we are given m potential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. We first present two optimal online algorithms with competitive ratios of 3/2 and 5/3 for m = 2, 3 cases, respectively. Then we present an online algorithm with a competitive ratio of at most 2 for general m ≥ 4, while the lower bound is 1.88.

We consider online scheduling of unit length jobs on m identical parallel-batch machines. Jobs arrive over time. The objective is to minimize maximum flow-time, with the flow-time of a job being the difference of its completion time and its release time. A parallel-batch machine can handle up to b jobs simultaneously as a batch. Here, the batch capacity is bounded, that is b < ∞. In this paper, we provide a best possible online algorithm for the problem with a competitive ratio of .

Batch processing machine scheduling in uncertain environment attracts more and more attention in the last decade. This paper deals with semi-online scheduling on two parallel batch processing machines with non-decreasing processing time of job. Jobs arrive over time in the online paradigm, and the processing time of any batch is equal to the length of the last arrival job in the batch. We study the unbounded model where each processing batch may contain an unlimited number of jobs, and the objective is to minimize the makespan. Given any job J_j together with its following job J_j+1, it is assumed that their processing times satisfy p_j+1 ≥ αp_j where α ≥ 1 is a constant. That is, jobs arrive in a non-decreasing order of processing times. We mainly propose an optimal ϕ-competitive online algorithm where ϕ ≥ 1 is a solution of equation ϕ³ + (α-1)ϕ² + (α² - α - 1)ϕ - α² = 0.

This paper studies the online hierarchical scheduling problem on two uniform machines with bounded job sizes, where the first machine M₁ receives both low and high hierarchy jobs, while the second machine M₂ only receives high hierarchy jobs. The machines have a speed ratio of s(s ≥ 1), and M₂ runs faster. Jobs are revealed one by one, and before the current job is scheduled, we have no information about next jobs except that the size of any job is in the interval [1, t]. The objective is to minimize the makespan. We present optimal algorithms for all (s, t) pairs.

This paper addresses online scheduling of malleable parallel jobs to minimize the maximum completion time, i.e., makespan. It is assumed that the execution time of a job J_j with processing time p_j is p_j/k + (k-1)c if the job is assigned to k machines, where c > 0 is a constant setup time. We consider online algorithms for the scheduling problem on two identical machines. Namely, the job J_j can be processed on one machine with execution time p_j or alternatively two machines in parallel with execution time p_j/2+c. For the asymptotical competitive ratio, we provide an improved online algorithm with makespan no more than (3/2)C* +c/2, where C* is the optimal makespan. For the strict competitive ratio, we propose an online algorithm with competitive ratio of 1.54, which is close to the lower bound of 1.5.

This paper studies the online preemptive scheduling of equal-length intervals on a single machine with lookahead. Let $p$ be the length (processing time) of all intervals. In the problem, at every time point $t$, online algorithms can foresee all the intervals that will arrive in the time segment $(t,t+L)$ for a certain $L$. When $L=p$, Zheng et al. [Comput- ers & Operations Research, 2013] established a lower bound of $\sqrt{2}$ and provided an online algorithm with a competitive ratio of 3. In this paper, we provide for this problem an improved online algorithm with a competitive ratio of 2.

An original online problem with decreasing profit growth rate is proposed to optimize the work hours of employees, named the online work-break problem (WBP). In this problem, the manager has to answer for an abstract worker when he should have a break for his work efficiency declines with the durative time of work period. The efficiency of the worker is presented by a work efficiency function $P(t)$ in the description of our problem. We present the online algorithms to solve the WBP based on linear estimation of $P(t)$ under two levels. Both the problems with single-period and dynamic multi-periods have 2-competitive online algorithms.

In this paper, we consider the online single machine scheduling problem to minimize the maximum starting time of the jobs. For the non-preemptive model, we show that there is no determined or randomized online algorithm with a bounded competitive ratio. For the preemption-resume model, we show that the well-known SRPT rule yields an optimal schedule. For the preemption-restart model, we show that any determined online algorithm has a competitive ratio of at least 2 and present an online algorithm with the best-possible competitive ratio of 2.

In this paper, we study an online scheduling on two parallel machines in MapReduce-like system where each job contains two kinds of tasks: map tasks and reduce tasks. A job’s reduce tasks can only be processed after all its map tasks are finished. We assume that the map tasks are fractional and the reduce tasks are preemptive. Our objective is to minimize makespan. We show that the lower bound for this MapReduce scheduling problem is $\sqrt{2}$. We then present an online algorithm with competitive ratio of $\sqrt{2}$ and thus it is optimal.

This paper studies online scheduling on $m$ identical parallel machines under the KRT environment, where jobs arrive over time and “KRT” means that in the online setting no jobs can be released when all of the machines are busy. The goal is to determine a feasible schedule to minimize the total of weighted completion times. When $m=1$, we prove that WSPT is an optimal online algorithm. When $m\ge 2$, we first present a lower bound $\frac{m^2-2+\sqrt{m^4-4m+4}}{2m(m-1)}$, and then show that WSPT is a 2-competitive online algorithm for the case $m=2$. For the case in which $m=2$ and all jobs have equal processing times, we provide a best possible online algorithm with a competitive ratio of $\frac{1+\sqrt{3}}{2}$.

In this paper, we consider the online scheduling of incompatible family jobs with equal length on an unbounded parallel-batch machine with job delivery. The jobs arrive online over time and belong to $f$ incompatible job families, where $f$ is known in advance. The jobs are first processed in batches on an unbounded parallel-batch machine and then the completed jobs are delivered in batches by a vehicle with infinite capacity to their customers. The jobs from distinct families cannot be processed and delivered in the same batch. The objective is to minimize the maximum delivery completion time of the jobs. For this problem, we present an online algorithm with the best competitive ratio of $1+\frac{\sqrt{4f^2+1}-1}{2f}$.