Abstract In medical appointment assignment, unit jobs representing patients arrive online and are assigned to a time slot within their given feasible time interval. We model this setting as interval-constrained online bipartite matching problem. We consider a variant of this problem where reassignments are allowed and extend it by a notion of time that is decoupled from the job arrival events. As jobs arrive, the current point in time gradually advances, and once the time of a slot is passed, the job assigned to it is fixed and cannot be reassigned anymore. We analyze two algorithms for this problem with respect to the resulting matching size and the number of occurring reassignments. We show that FirstFit with reassignments according to the shortest augmenting path rule is exactly $$\frac{2}{3}$$ 2 3 -competitive with respect to the matching cardinality. The competitive ratio remains $$\frac{2}{3}$$ 2 3 if we restrict FirstFit to consider only augmenting paths causing at most a constant number of reassignments, which implies a linear number of reassignments in total. This fills the gap between the known optimal algorithm with no reassignments at all, which is $$\frac{1}{2}$$ 1 2 -competitive, on the one hand, and an earliest-deadline-first strategy (EDF), which we prove to be 1-competitive in our over-time framework, but which suffers $$\Omega (n^2)$$ Ω ( n 2 ) reassignments in the worst case, on the other. We further extend the problem setting to the sets of feasible slots per job that are not intervals. In this setting, FirstFit remains $$\frac{2}{3}$$ 2 3 -competitive, which is optimal with respect to the matching cardinality, while EDF loses its optimality.

Algorithms for computing fractional solutions to the quickest transshipment problem have been significantly improved since Hoppe and Tardos first solved the problem in strongly polynomial time. For integral solutions, runtime improvements are limited to general progress on submodular function minimization, which is an integral part of Hoppe and Tardos' algorithm. Yet, no structural improvements on their algorithm itself have been proposed. We replace two central subroutines in the algorithm with methods that require vastly fewer minimizations of submodular functions. This improves the state-of-the-art runtime from $ \tilde{O}(m^4 k^{15}) $ down to $ \tilde{O}(m^2 k^5 + m^4 k^2) $, where $ k $ is the number of terminals and $ m $ is the number of arcs.

ABSTRACT Peak cost is a novel objective for flows over time that describes the amount of workforce necessary to run a system. We focus on minimizing peak costs in the context of maximum temporally repeated flows and formulate the corresponding MPC‐MTRF problem. First, we discuss the limitations that emerge when restricting the solution space to integral temporally repeated flows, which is motivated by practical applications. We show that, in general, MPC‐MTRF has an integrality gap of and an arbitrarily bad approximation ratio compared to general flows over time. We proceed with a complexity analysis for MPC‐MTRF and show that both the decision version and the optimization version of integral MPC‐MTRF are strongly ‐hard, even under strong restrictions. On the positive side, we identify two special cases that are solvable in polynomial time: unit‐cost series‐parallel networks and networks with time horizon at least twice as long as the longest path in the network with respect to the transit time. Moreover, in both cases, we provide an explicit algorithm that constructs an integral optimal solution.

In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval, and each job has a specific time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We extend ISMA by introducing machine capacities and flexible machine end times. Using machine capacities we model parallel processing of multiple jobs per machine, which leads to the Multithread Interval Scheduling with Machine Availabilities (MISMA). Limited machine availabilities are usually due to maintenance. Time slots for maintenance at the end of a processing period are often predetermined by staff schedules before the slots are assigned to specific machines. This motivates a variant of MISMA in which the end times of the machines’ availability intervals can be permuted, the Flexible Multithread ISMA (FLEXMISMA). In this paper, we determine a tight classification of conditions that are required for obtaining a polynomial-time algorithm for both MISMA and FLEXMISMA. More specifically, we show that FLEXMISMA is at least as hard as MISMA. For FLEXMISMA, we present polynomial-time algorithms for instances (i) with at most two available machines at a time, and (ii) with constantly many parallel jobs at each point in time, which both also solve MISMA; (iii) with arbitrarily many machines of capacity one each, in which case MISMA is known to be NP-hard; and (iv) with jobs having length one or two, for which the complexity of MISMA remains open Furthermore, we complement result (i) by showing that both problems are NP-hard already for instances with three machines as a special case of the Vertex-Disjoint Paths problem. In contrast to (iii), we prove that increasing the capacity of machines from one to two renders FLEXMISMA NP-hard as well for arbitrarily many machines.

Abstract The minimum color‐degree perfect b‐matching problem (Col‐BM) is a new extension of the perfect b‐matching problem to edge‐colored graphs. The objective of Col‐BM is to minimize the maximum number of differently colored edges in a perfect b‐matching that are incident to the same node. We show that Col‐BM is ‐hard on bipartite graphs by a reduction from (3,B2)‐Sat, and conclude that there exists no (2 − ϵ)‐approximation algorithm unless . However, we identify a class of two‐colored complete bipartite graphs on which we can solve Col‐BM in polynomial time. Furthermore, we use dynamic programming to devise polynomial‐time algorithms solving Col‐BM with a fixed number of colors on series‐parallel graphs and simple graphs with bounded treewidth.