This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system (E,ℐ), a schedule consists of an independent set I_t ∈ ℐ for every time step t ∈ ℕ, with the objective of fulfilling frequency requirements on the occurrence of elements in E. We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates g(e) for e ∈ E and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. We assume that g is normalized so that it is a convex combination of the incidence vectors of ℐ. Using the integrality of the matroid-intersection polytope, we prove that, when (E,ℐ) is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. We complement this existential result with efficient algorithms for specific matroid classes, achieving a maximum height of 2 for uniform and partition matroids, and 4 for graphic and laminar matroids. In contrast, we show that for general independence systems, the optimal guaranteed height is Θ(log |E|) and can be achieved by an efficient algorithm. For combinatorial pinwheel scheduling, where each element e ∈ E needs to occur in the schedule at least every a_e ∈ ℕ time steps, our results imply bounds on the density sufficient for schedulability.

We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right, and the packet arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the elapsed time between its release and its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al. in 2014, with a focus on line networks. They proposed several natural algorithms. For one, they proved that it is not O(1)-competitive; for others, they claimed analogous lower bounds, seemingly leaving no natural candidate for an O(1)-competitive algorithm. In this paper, we study a natural algorithm not considered in that work. Our algorithm, simply called Greedy, selects packets according to their projected flow time under the assumption that they are not delayed any further. We focus on the special case in which each packet needs to be forwarded by one or two routers; this case captures core difficulties. We show that Greedy achieves a competitive ratio of exactly 2-2^{1-k}, where k is the number of active routers in the network. We also give the first nontrivial general lower bound, which applies even to randomized algorithms: using the same type of instances as in our lower bound for Greedy, we show that no algorithm can be (4/3-ε)-competitive for any ε > 0.

We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid \(\mathcal{M}\) (in compact representation) on ground set \(E\) is given, and each element \(i \in E\) is active independently with known probability \(p_i \in (0,1)\). The elements can be queried, upon which it is revealed whether the respective element is active or not. The goal is to find an adaptive querying strategy for determining whether there is a basis of \(\mathcal{M}\) in which all elements are active, with the objective of minimizing the expected number of queries.

Abstract. A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a [Formula: see text]-approximation for any [Formula: see text] for the general case. On instances where the vertex weights are binary, we achieve a [Formula: see text]-approximation. Finally, we develop a polynomial-time approximation scheme for Euclidean graphs. Previously, only an 8-approximation was known for all these cases.

We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of $k$-of-$n$ functions: There are independent Boolean random variables $x_1,\dots,x_n$ where each variable $i$ has a known probability $p_i$ of taking value $1$, and a known cost $c_i$ that can be paid to find out its value. The value of the function is $1$ iff there are at least $k$ $1$s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of $2$ on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of $3/2$ for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument. In fact, our PTAS extends to the class of arbitrary symmetric Boolean functions, which are Boolean functions whose value only depends on the number of $1$s among the input variables.

This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of jobs with stochastic processing times on parallel identical machines. When all processing times follow Bernoulli-type distributions, Gupta et al. in 2023 exhibited approximation algorithms, improving upon an earlier algorithm by Eberle et al. for a special case. Both approximation guarantees depend on the number of machines. The present paper shows that, quite unexpectedly, the problem with Bernoulli-type jobs admits a PTAS whenever the number of different job-size parameters is bounded by a constant. The result is based on a series of transformations of an optimal scheduling policy to a "stratified" policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal stratified policy is computed using dynamic programming. Two technical issues are solved, namely (i) to ensure that, with at most a slight delay, the stratified policy has an information advantage over the optimal policy, allowing it to simulate its decisions, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our results also imply a quasi-polynomial approximation algorithm with a guarantee logarithmic in the number of jobs for the case with an arbitrary number of job sizes.

We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a search task is delegated to an agent. The agent performs a sequential exploration of n boxes, suffers the exploration cost for each inspected box, and selects the content (called the prize) of one inspected box as outcome. Agent and principal obtain an individual value based on the selected prize. To influence the search, the principal a-priori designs a contract with a non-negative payment to the agent for each potential prize. The goal of the principal is to maximize her expected reward, i.e., value minus payment. Interestingly, this natural contract scenario shares close relations with the Pandora’s Box problem. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass is that of linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we obtain optimal contracts under the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. More generally, for general contracts with non-zero agent values for outcomes we show how to compute an optimal contract in two cases: (1) when each box has only one prize with non-zero value for principal and agent, (2) for i.i.d. boxes with a single prize with positive value for the principal.

We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only after all jobs are assigned to a given number of bags, the actual number of machines is revealed. Subsequently, the jobs need to be assigned to the machines without splitting the bags. This is the stochastic version of a related problem introduced by Stein and Zhong [SODA 2018, TALG 2020] and it is, for example, motivated by bundling jobs that need to be scheduled by data centers. We present two PTASs for the stochastic setting, computing job-to-bag assignments that (i) minimize the expected maximum machine load and (ii) maximize the expected minimum machine load (like in the Santa Claus problem), respectively. The former result follows by careful enumeration combined with known PTASs. For the latter result, we introduce an intricate dynamic program that we apply to a suitably rounded instance.

This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absolute or relative, depending on the version) wins. After the voters have made their choices, each vote can be inspected to determine which candidate received that vote. The time (or cost) to inspect each of the votes is known in advance. The task is to (possibly adaptively) determine the order in which to inspect the votes, so as to minimize the expected time to determine which candidate has won the election. We design polynomial-Time constant-factor approximation algorithms for both the absolute-majority and the relative-majority version. Both algorithms are based on a two-phase approach. In the first phase, the algorithms reduce the number of relevant candidates to O(1), and in the second phase they utilize techniques from the literature on stochastic function evaluation to handle the remaining candidates. In the case of absolute majority, we show that the same can be achieved with only two rounds of adaptivity.

Abstract. We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals whether the realized value is smaller or larger than the [Formula: see text]-quantile of the underlying distribution of some constant [Formula: see text]. Subsequent tests allow us to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow us to maximize the expected value of the chosen item. We study both identical and nonidentical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios.

Abstract. We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given [Formula: see text] tests. Each test [Formula: see text] can be conducted at cost [Formula: see text], and it succeeds independently with probability [Formula: see text]. Further, a partition of the (integer) interval [Formula: see text] into [Formula: see text] smaller intervals is known. The goal is to conduct tests so as to determine that interval from the partition in which the number of successful tests lies while minimizing the expected cost. Ghuge, Gupta, and Nagarajan (IPCO 2022) recently showed that a polynomial-time constant-factor approximation algorithm exists. We show that interweaving the two strategies that order tests increasingly by their [Formula: see text] and [Formula: see text] ratios, respectively—as already proposed by Gkensosis et al. for a special case—yields a small approximation ratio. We also show that the approximation ratio can be slightly decreased from 6 to [Formula: see text] by adding in a third strategy that simply orders tests increasingly by their costs. The similar analyses for both algorithms are nontrivial but arguably clean. Finally, we complement the implied upper bound of [Formula: see text] on the adaptivity gap with a lower bound of 3/2. Since the lower-bound instance is a so-called unit-cost [Formula: see text]-of-[Formula: see text] instance, we settle the adaptivity gap in this case.

We study threshold testing, an elementary probing model with the goal to choose a large value out of n i.i.d. random variables. An algorithm can test each variable X_i once for some threshold t_i, and the test returns binary feedback whether X_i ≥ t_i or not. Thresholds can be chosen adaptively or non-adaptively by the algorithm. Given the results for the tests of each variable, we then select the variable with highest conditional expectation. We compare the expected value obtained by the testing algorithm with expected maximum of the variables. Threshold testing is a semi-online variant of the gambler’s problem and prophet inequalities. Indeed, the optimal performance of non-adaptive algorithms for threshold testing is governed by the standard i.i.d. prophet inequality of approximately 0.745 + o(1) as n → ∞. We show how adaptive algorithms can significantly improve upon this ratio. Our adaptive testing strategy guarantees a competitive ratio of at least 0.869 - o(1). Moreover, we show that there are distributions that admit only a constant ratio c < 1, even when n → ∞. Finally, when each box can be tested multiple times (with n tests in total), we design an algorithm that achieves a ratio of 1 - o(1).

A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a (2e+ε)-approximation for any ε > 0. For the case that all vertices have unit weight, we provide a 2e-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an 8-approximation was known.

We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also describes how to gradually grow the solution as the cardinality bound increases. The goal is to find an incremental solution that guarantees a good competitive ratio against the optimum solution for all cardinalities simultaneously. The central challenge is to characterize maximization problems where this is possible, and to determine the best-possible competitive ratio that can be attained. A lower bound of 2.18 and an upper bound of φ + 1 ≈ 2.618 are known on the competitive ratio for monotone and accountable objectives [Bernstein et al., Math. Prog., 2022], which capture a wide range of maximization problems. We introduce a continuization technique and identify an optimal incremental algorithm that provides strong evidence that φ+1 is the best-possible competitive ratio. Using this continuization, we obtain an improved lower bound of 2.246 by studying a particular recurrence relation whose characteristic polynomial has complex roots exactly beyond the lower bound. Based on the optimal continuous algorithm combined with a scaling approach, we also provide a 1.772-competitive randomized algorithm. We complement this by a randomized lower bound of 1.447 via Yao’s principle.

In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already; or it can decide to sell and collect the current price as a reward if it holds the item.

We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require that jobs contain some slack ɛ > 0, which means that the feasible time window for scheduling a job is at least 1+ɛ times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services, and disallows last-minute rejections of critical tasks. We present an algorithm for unrelated machines that is \(\Theta (\frac{1}{\varepsilon })\) -competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of \(\mathcal {O}(\frac{1}{\varepsilon - \delta })\) for 0 < δ < ɛ. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines.

We revisit Depth-First Proof-Number Search (DFPN), a well-known algorithm for solving two-player games. First, we consider the completeness property of the algorithm and its variants, i.e., whether they always find a winning strategy when there exists one. While it is known that the standard version is not complete, we show that the combination with the simple Threshold Controlling Algorithm is complete, solving an open problem from the area. Second, we modify DFPN to compute a diverse set of solutions rather than just a single one. Finally, we apply this new variant in Chemistry to the synthesis planning of new target molecules (Retrosynthesis). In this domain a diverse set of many solutions is desirable. We apply additional modifications from the literature to the algorithm and show that it outperforms Monte-Carlo Tree-Search, another well-known algorithm for the same problem, according to a natural diversity measure.

We consider the online search problem in which a server starting at the origin of a d-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the d-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in Ω(d)∩O(d3/2).

A prophet inequality states, for some $α\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $α$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $βn$ samples for some $β\geq 0$. We first give improved lower bounds on $α$ for a wide range of values of $β$; specifically, $α\geq(1+β)/e$ when $β\leq 1/(e-1)$, which is tight, and $α\geq 0.648$ when $β=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.

Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as subset maximization problems: One is given a ground set $$N=\{1,\dots ,n\}$$ , a collection $$\mathcal {F}\subseteq 2^N$$ of subsets thereof such that $$\emptyset \in \mathcal {F}$$ , and an objective (profit) function $$p:\mathcal {F}\rightarrow \mathbb {R}_+$$ . The task is to choose a set $$S\in \mathcal {F}$$ that maximizes p(S). We consider the multistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function $$p_t$$ (and possibly the set of feasible solutions $$\mathcal {F}_t$$ ) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the trade-off between good per-time solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the online setting, that is, $$p_t$$ (along with possibly $$\mathcal {F}_t$$ ) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constant-competitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online D IAL -A-R IDE problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O ( n 2 ) for closed offline TSP on the line with release dates and show that both variants of offline D IAL -A-R IDE on the line are NP-hard for any capacity c ≥ 2 of the server.

We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on m machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis, it is commonly required that jobs contain some slack ε > 0, which means that the feasible time window for scheduling a job is at least 1+ε times its processing time. In this paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services and disallows last-minute rejections of critical tasks. We present the first online algorithm for handling commitment on parallel machines for arbitrary slack ε. When the scheduler must commit upon starting a job, the algorithm is Θ(1/ε)-competitive. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of 𝒪(1/(ε - δ)) for 0 < δ < ε. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithms admits any bounded competitive ratio.

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [27{, which gives rise to studying more tractable special cases of the problem. In this article, we focus on the fundamental special case of regions that are hyperplanes in the d -dimensional Euclidean space. This case contrasts the much-better understood case of so-called fat regions [20, 40{. While for d = 2, an exact algorithm with a running time of O(n 5 ) is known [34{, settling the exact approximability of the problem for d = 3 has been repeatedly posed as an open question [29, 30, 40, 47{. To date, only an approximation algorithm with guarantee exponential in d is known [30{, and NP-hardness remains open. For arbitrary fixed d , we develop a Polynomial Time Approximation Scheme (PTAS) that works for both the tour and path version of the problem. Our algorithm is based on approximating the convex hull of an optimal tour by a convex polytope of bounded complexity. After enumerating a number of structural properties of these polytopes, a linear program finds one of them that minimizes the length of the tour. As the approximation guarantee approaches 1, our scheme adjusts the complexity of the considered polytopes accordingly. In the analysis of our approximation scheme, we show that our search space includes a sufficiently good approximation of the optimum. To do so, we develop a novel and general sparsification technique that transforms an arbitrary convex polytope into one with a constant number of vertices, and, subsequently, into one of bounded complexity in the above sense. We show that this transformation does not increase the tour length by too much, while the transformed tour visits any hyperplane that it visited before the transformation.

We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [20], which gives rise to studying more tractable special cases of the problem. In this paper, we focus on the fundamental special case of regions that are hyperplanes in the d-dimensional Euclidean space. This case contrasts the much-better understood case of so-called fat regions [16, 34]. While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approximability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], and NP-hardness remains open. For arbitrary fixed d, we develop a Polynomial Time Approximation Scheme (PTAS) that works for both the tour and path version of the problem. Our algorithm is based on approximating the convex hull of the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties of the tour. As the approximation guarantee approaches 1, our scheme adjusts the complexity of the considered polytopes accordingly. In the analysis of our approximation scheme, we show that our search space includes a sufficiently good approximation of the optimum. To do so, we develop a novel and general sparsification technique to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.

We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general $\mathcal{O}(\log {m})$-competitive algorithm for the online problem, where $m$ is the optimal number of machines used in an offline solution. This is the first improvement to an intriguing problem in nearly two decades. To date, the best known result is a $\mathcal{O}(\log (p_{\max}/p_{\min}))$-competitive algorithm by Phillips et al. [ Optimal time-critical scheduling via resource augmentation, STOC, 1997] that depends on the ratio of maximum and minimum job sizes, $p_{\max}$ and $p_{\min}$. Even for $m=2$ no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of $\mathcal{O}(1)$ even independently of $m$. The following two key components lead to our new result. First, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online Dial-A-Ride problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O(n2) for closed offline TSP on the line with release dates and show that both variants of offline Dial-A-Ride on the line are NP-hard for any capacity c ≥ 2 of the server.

We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general ℴ(log m)-competitive algorithm for the online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an intriguing problem in nearly two decades. To date, the best known result is a ℴ(log(pmax/pmin))-competitive algorithm by Phillips et al. (STOC 1997) that depends on the ratio of maximum and minimum job sizes, pmax and pmin. Even for m = 2 no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of ℴ(1) even independently of m. The following two key components lead to our new result. Firstly, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.

In this paper we investigate the power of migration in online scheduling on multiple parallel machines. The problem is to schedule preemptable jobs with release dates and deadlines on a minimum number of machines. We show that migration, that is, allowing that a preempted job is continued on a different machine, has a huge impact on the performance of a schedule. More precisely, let m be the number of machines required by a migratory solution; then the increase in the number of machines when disallowing migration is unbounded in m. This complements and strongly contrasts previous results on variants of this problem. In both the offline variant and a model allowing extra speed, the power of migration is limited as the increase of number of machines and speed, respectively, can be bounded by a small constant.

Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs). We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.

We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time is a location on the real line. At each integer time, a convex function arrives online. In response, the online algorithm picks a new location. The cost paid by the online algorithm for this response is the distance moved plus the value of the function at the final destination. The objective is then to minimize the aggregate cost over all time. The motivating application is rightsizing power-proportional data centers. We give a 2-competitive algorithm for this problem. We also give a 3-competitive memoryless algorithm, and show that this is the best competitive ratio achievable by a deterministic memoryless algorithm. Finally we show that this online problem is strictly harder than the standard ski rental problem.

Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs). We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.