Abstract. In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and nonpreemptive version of the problem. We achieve this by presenting a new algorithm called [Formula: see text]. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural [Formula: see text] algorithm. Furthermore, we provide matching lower bounds on the competitive ratio of [Formula: see text], which yields that our analysis is tight.

Abstract. We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most [Formula: see text], under the assumption that the values of singleton sets are in the range [Formula: see text], and we give a lower bound of [Formula: see text] on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of [Formula: see text] and an upper bound of [Formula: see text] for the incremental maximization of classical flows with capacities in [Formula: see text] which is tight for the unit capacity case.

Abstract. We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of [Formula: see text]-[Formula: see text]-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, [Formula: see text]-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient—as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of [Formula: see text] on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for [Formula: see text]-augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953–979] by obtaining a tight lower bound for [Formula: see text]-augmentable functions for all [Formula: see text]. For weighted rank functions of independence systems, our tight bound becomes [Formula: see text], which recovers the known bound of [Formula: see text] for independence systems of rank quotient at least [Formula: see text].

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.