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.

Context: Computer science, even now, attracts a small number of women, and the proportion of women in the field decreases through advancing career stages. Consequently, few women progress to Ph.D. studies in computer science after completing master’s studies. Empowering women at this stage in their careers is essential, not just for equality reasons, but to unlock untapped potential for society, industry and academia. Objective: This paper aims to identify students’ career assumptions and information related to Ph.D. studies focused on gender-based differences. We propose a program to inform female master students about Ph.D. studies that explains the process, clarifies misconceptions, and alleviates concerns. Method: An extensive survey was conducted to identify factors that encourage and discourage students from undertaking Ph.D. studies. The analysis identified statistically significant differences between those who undertook Ph.D. studies and those who did not, as well as statistically significant gender differences. A catalogue of questions to initiate discussions with potential Ph.D. students which allowed them to explore these factors was developed. These were structured into a Women’s Career Lunch program where students can explore and discuss the benefits of Ph.D. study. Results: Encouraging factors towards Ph.D. study include interest and confidence in research arising from a research involvement during earlier studies; enthusiasm for and self-confidence in computer science in addition to an interest in an academic career; encouragement from external sources; and a positive perception towards Ph.D. studies which can involve achieving personal goals. Discouraging factors include uncertainty and lack of knowledge of the Ph.D. process, a perception of lower job flexibility, and the requirement for long-term commitment. Gender differences highlighted that female students who pursue a Ph.D. have less confidence in their technical skills than males but a higher preference for interdisciplinary areas. Female students are less inclined than males to perceive the industry as offering better job opportunities and more flexible career paths than academia. Conclusions: The insights collected from the survey facilitated the development of a questions catalogue structured into the Women Career Lunch program to help students make a more informed decision concerning whether they should pursue a Ph.D. in computer science. Localised versions of this program, in 8 languages, were created to support its adoption in different countries and assist in mitigating the female under-representation challenge.

ABSTRACT In this article, we motivate and define variants of perfect matching under precedence constraints where a perfect matching is built incrementally and precedence constraints ensure that an edge may only be added to the matching if the edge's predecessor vertices have already been covered. We study the complexity of the problem and particularly consider ‐canonical precedence constraints where only edges that are “close” to the current matching may be added to the matching. For the ‐hard perfect matching under 1‐canonical precedence constraints, we identify polynomial‐time solvable cases.

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.

We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the sum of completion times (P|gen-prec, p_j = 1|γ, γ ∈ {C_max,∑_jC_j}). In our setting, each job is equipped with a Boolean formula (precedence constraint) over the set of jobs. A schedule satisfies a job’s precedence constraint if setting earlier jobs to true satisfies the formula. Our definition generalizes several common types of precedence constraints: classical and-constraints if every formula is a conjunction, or-constraints if every formula is a disjunction, and and/or-constraints if every formula is in conjunctive normal form. We prove fixed-parameter tractability when parameterizing by the number of predecessors. For parameterization by the number of successors, however, the complexity depends on the structure of the precedence constraints. If every constraint is a conjunction or a disjunction, we prove the problem to be fixed-parameter tractable. For constraints in disjunctive normal form, we prove W[1]-hardness. We show that the and/or-constrained problem is NP-hard, even for a single successor. Moreover, we prove NP-hardness on two machines if every constraint is a conjunction or a disjunction. This result not only proves para-NP-hardness for parameterization by the number of machines but also complements the polynomial-time solvability on two machines if every constraint is a conjunction [Coffman and Graham, 1972] or if every constraint is a disjunction [Johannes, 2005].

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.

ABSTRACT We propose a variant of the shortest path problem where the order in which vertices occur in the path is subject to precedence constraints. Precedence constraints are defined in terms of vertex pairs which indicate that a vertex is the predecessor of a vertex . A feasible (not necessarily simple) path may visit a vertex only upon having covered all its predecessors. The problem generalizes the graphic TSP Path, which makes it APX‐hard. We propose a dynamic program and identify input classes for which the dynamic program yields an optimal solution in polynomial time. We also explore the limits of efficient solvability by proving that the problem remains hard even when significantly restricting the structure of the graph or the structure of the precedence constraints: Surprisingly, the problem remains hard even when restricted to spiders.

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 In this article, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so‐called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc, we require equal flow for all scenarios. The objective is to minimize the maximum cost occurring among all scenarios. We show that the problem is strongly ‐complete on acyclic digraphs by a reduction from the ‐Sat problem. Furthermore, we prove that the problem is weakly ‐complete on series‐parallel digraphs by a reduction from a special case of the Partition problem. If in addition the number of scenarios is constant, we observe the pseudo‐polynomial‐time solvability of the problem. We provide poly‐nomial‐time algorithms for three special cases on series‐parallel digraphs. Finally, we present a polynomial‐time algorithm for pearl digraphs.

Abstract Because of the long planning periods and their long life cycle, railway infrastructure has to be outlined long ahead. At the present, the infrastructure is designed while only little about the intended operation is known. Hence, the timetable and the operation are adjusted to the infrastructure. Since space, time and money for extension measures of railway infrastructure are limited, each modification has to be done carefully and long lasting and should be appropriate for the future unknown demand. To take this into account, we present the robust network design problem for railway infrastructure under capacity constraints and uncertain timetables. Here, we plan the required expansion measures for an uncertain long‐term timetable. We show that this problem is NP‐hard even when restricted to bipartite graphs and very simple timetables and present easier solvable special cases. This problem corresponds to the fixed‐charge network design problem where the expansion costs are minimized such that the timetable is conductible. We model this problem by an integer linear program using time expanded networks. To incorporate the uncertainty of the future timetable, we use a scenario‐based approach. We define scenarios with individual departure and arrival times and optional trains. The network is then optimized such that a given percentage of the scenarios can be operated while minimizing the expansion costs and potential penalty costs for not scheduled optional trains.

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.

Special issue on network analytics

The potential for mHealth solutions is steadily increasing due to an enormous growth in the area of mobile networks and the mobile Internet. However, not only the general connection is becoming faster and more stable, but also the mobile devices themselves are becoming even more advanced. Nowadays, these devices are able to acquire physiological data and transfer them to e.g. a physician or technician to be analyzed before an actual appointment. Using these technological advantages, more and more evidence could be used for diagnosis and treatment. Instead, long preparation and delay are part of everyday practice nowadays and information and data acquisition take up much time before diagnosis.This paper describes a general concept for a centralized screening / pre-diagnosis system for mobile sleep laboratories. The system is designed to have as little influence as possible on the usual sleep environment, but still allows a medically usable recording of sleep activities and health parameters. Furthermore, the concept covers the access possibilities of the attending physician as well as the back-flow of a final diagnosis. Finally, we report on the resulting challenges of such systems with respect to privacy.

The multi‐budgeted matching problem (mBM) is a weighted matching problem with independent edge cost functions. For each cost function, a budget constraint requires the accumulated cost not to exceed a corresponding budget. We show that the mBM is strongly NP‐hard on paths with uniform edge weights and budgets by a reduction from 3‐SAT. Subsequently, we propose a dynamic program for series‐parallel graphs with pseudo‐polynomial run time for a fixed number of budget constraints. As an extension we show how this algorithm can be used to solve the mBM on trees using a graph transformation. Realizing that both these graph classes have a bounded treewidth in common, we introduce a dynamic program based on tree decompositions. This approach leads to a pseudo‐polynomial algorithm for the mBM with fixed on graphs of bounded treewidth.

Flexgrid optical networking technology allows for a more flexible consumption of bandwidth. The spectrum allocation problem consists of the conflict‐free assignment of consecutive spectrum space of different sizes to lightpaths. In this article, we study the computational complexity of spectrum allocation with and without demand uncertainty. First, it is shown that the problem becomes already NP‐hard for cases where wavelength assignment is still polynomial time solvable. Next, five different ways to define the robust counterpart are compared. It is shown (amongst others) that on a single network edge, the two least efficient models are less computationally demanding than the other variants. A computational study using comparable integer linear programming formulations reveals that the additional slots required by these models directly depend on the restrictions of the employed technology. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 342–359 2017

The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing one to reduce the cost of at most K arcs. In this article, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3‐SAT we prove strong ‐completeness and inapproximability, even on directed acyclic graphs. On the positive side, we identify three polynomially solvable cases: on arborescences, on so‐called tree‐like graphs, and on instances with a constant number of sinks. Furthermore, we develop dynamic programs with pseudo‐polynomial running time for the BMCF(K) problem on (directed) series‐parallel graphs and (directed) graphs of bounded treewidth. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 67–82 2017

Abstract In this article, we investigate two different recoverable robust (RR) models to deal with cost uncertainties in a shortest path problem. RR extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen. Thus, the parameter k can be interpreted as a mediator between robust optimization—no changes allowed—and optimization on the fly—an arbitrary solution can be chosen. Considering three classical scenario sets, which model uncertainties in the cost function, we show that this new problem is strongly NP‐hard in all these cases and is not approximable, unless P = NP. This is in contrast to the robust shortest path problem, where, for example, an optimal solution can be computed efficiently for interval and Γ ‐scenarios. For series‐parallel graphs and interval scenarios, we present a polynomial time algorithm for this RR setting. In our second model, the recovery set, that is, the set of paths selectable in the second stage is not limited, but deviating from the previous choice comes at extra cost. Thus, a path chosen in the first stage produces renting costs modeled as an α ‐fraction of the scenario cost. For an arc taken in the second stage, the remaining cost needs to be paid in addition to some extra inflation cost modeled by a β ‐fraction of the scenario cost, if the arc was not reserved beforehand. The complexity status of this problem is similar to the robust case. Yet, for Γ ‐scenarios, the problem is again strongly NP ‐hard, but can be approximated with a \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\min\{2+\beta,\frac{1}{\alpha}\}$\end{document} factor. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract We consider a basic subproblem which arises in line planning, and is of particular importance in the context of a high system load or robustness: How much can be routed maximally along all possible lines? The essence of this problem is the path constrained network flow (PCN) problem. We explore the complexity of this problem and its dual. In particular we show for the primal that it is as hard to approximate as MAX CLIQUE and for the dual that it is as hard to approximate as SET COVER. We also prove that the PCN problem is hard for special graph classes, interesting both from a complexity and from a practical perspective. Finally, we present a special graph class for which there is a polynomial‐time algorithm. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011