Search

We consider a 1-machine scheduling problem where the temperature of a job rises during processing, and cools down when not being processed according to given linear heating and cooling rates. No job's temperature is allowed to rise above a given threshold, and no job's temperature can cool below 0. Another crucial property of our problem is that jobs can be preempted an arbitrary number of times, and even more, we allow that a job is processed for an infinitely small amount of time. We consider two objectives: minimize the makespan, and minimize the sum of completion times. Our results are as follows. We show how to compactly represent a solution. Further, we prove that the problem of minimizing the sum of completion times can be solved in polynomial time by formulating it as a linear program, and deriving a structural property. This result can be extended to hold for any number of machines. Further, we show that a minimum makespan can be found in $O(n)$ time, even when heating and cooling rates are job-dependent.

Recently, many studies have been devoted to finding \textit{diverse} solutions in classical combinatorial problems, such as \textsc{Vertex Cover} (Baste et al., IJCAI'20), \textsc{Matching} (Fomin et al., ISAAC'20) and \textsc{Spanning Tree} (Hanaka et al., AAAI'21). We initiate the algorithmic study of $k$-\textsc{Diverse Minimum s-t Cuts} which, given a directed graph $G = (V, E)$, two specified vertices $s,t \in V$, and an integer $k > 0$, asks for a collection of $k$ minimum $s$-$t$ cuts in $G$ that has maximum diversity. We investigate the complexity of the problem for maximizing three diversity measures that can be applied to a collection of cuts: (i) the sum of all pairwise Hamming distances, (ii) the cardinality of the union of cuts in the collection, and (iii) the minimum pairwise Hamming distance. We prove that $k$-\textsc{Diverse Minimum s-t Cuts} can be solved in strongly polynomial time for diversity measures (i) and (ii) via \textit{submodular function minimization}. We obtain this result by establishing a connection between ordered collections of minimum $s$-$t$ cuts and the theory of distributive lattices. When restricted to finding only collections of mutually disjoint solutions, we provide a more practical algorithm that finds a maximum set of pairwise disjoint minimum $s$-$t$ cuts. For graphs with small minimum $s$-$t$ cut, it runs in the time of a single \textit{max-flow} computation. Our results stand in contrast to the problem of finding $k$ diverse \textit{global} minimum cuts -- which is known to be NP-hard even for the disjoint case (Hanaka et al., AAAI'23) -- and partially answer a long-standing open question of Wagner (Networks, 1990) about improving the complexity of finding disjoint collections of minimum $s$-$t$ cuts. Lastly, we show that $k$-\textsc{Diverse Minimum s-t Cuts} subject to diversity measure (iii) is NP-hard already for $k=3$., Comment: An earlier version of this works appeared at the 34th International Symposium on Algorithms and Computation (ISAAC 2023). Corrected typos in Section 3 and revised arguments in Section 4. Results unchanged. Added new complexity results in Section 5

We investigate a new tournament format that consists of a series of individual knockout tournaments; we call this new format a Serial Knockout Competition (SKC). This format has recently been adopted by the Professional Darts Corporation. Depending on the seedings of the players used for each of the knockout tournaments, players can meet in the various rounds (eg first round, second round, ..., semi-final, final) of the knockout tournaments. Following a fairness principle of treating all players equal, we identify an attractive property of an SKC: each pair of players should potentially meet equally often in each of the rounds of the SKC. If the seedings are such that this property is indeed present, we call the resulting SKC stable. In this note we formalize this notion, and we address the question: do there exist seedings for each of the knockout tournaments such that the resulting SKC is stable? We show, using a connection to the Fano plane, that the answer is yes for 8 players. We show how to generalize this to any number of players that is a power of 2, and we provide stable schedules for competitions on 16 and 32 players

Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than the other formulations, while its LP relaxation is still being solvable in polynomial time. In addition, we provide an exponentially sized class of valid inequalities for the matching formulation. Complementing our theoretical assessment of the strength of the different formulations, we also experimentally show that the matching formulation is superior on a broad set of instances. Finally, we describe a branch-and-price algorithm for finding round robin tournaments that is based on the matching formulation.

For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.

Kidney exchange programs (KEPs) form an innovative approach to increasing the donor pool through allowing the participation of renal patients together with a willing but incompatible donor. The aim of a KEP is to identify groups of incompatible donor-recipient pairs that could exchange donors leading to feasible transplants. As the size of a kidney exchange grows, a larger proportion of participants can be transplanted. Collaboration between multiple transplant centers, by merging their separate kidney exchange pools is thus desirable. As each transplant center has its own interest to provide the best care to its own patients, collaboration requires balancing individual and common objectives. We consider a class of algorithmic mechanisms for multi-center kidney exchange programs we call rejection-proof mechanisms. Such mechanisms propose solutions with the property that no player wishes to unilaterally deviate. We provide a mechanism optimizing social value under this restriction, though the underlying optimization problem is Sigma-2-p-Hard. We also describe a computationally easier but sub-optimal alternative. Experiments show that rejection-proofness can be achieved at limited cost compared to optimal solutions for regular kidney exchange. Computationally, we provide algorithms to compute optimal rejection-proof solutions for small and medium instance sizes.

Let $P$ be a set of points in $\mathbb{R}^d$, where each point $p\in P$ has an associated transmission range $\rho(p)$. The range assignment $\rho$ induces a directed communication graph $\mathcal{G}_{\rho}(P)$ on $P$, which contains an edge $(p,q)$ iff $|pq| \leq \rho(p)$. In the broadcast range-assignment problem, the goal is to assign the ranges such that $\mathcal{G}_{\rho}(P)$ contains an arborescence rooted at a designated node and whose cost $\sum_{p \in P} \rho(p)^2$ is minimized. We study trade-offs between the stability of the solution -- the number of ranges that are modified when a point is inserted into or deleted from $P$ -- and its approximation ratio. We introduce $k$-stable algorithms, which are algorithms that modify the range of at most $k$ points when they update the solution. We also introduce the concept of a stable approximation scheme (SAS). A SAS is an update algorithm that, for any given fixed parameter $\varepsilon>0$, is $k(\epsilon)$-stable and maintains a solution with approximation ratio $1+\varepsilon$, where the stability parameter $k(\varepsilon)$ only depends on $\varepsilon$ and not on the size of $P$. We study such trade-offs in three settings. - In $\mathbb{R}^1$, we present a SAS with $k(\varepsilon)=O(1/\varepsilon)$, which we show is tight in the worst case. We also present a 1-stable $(6+2\sqrt{5})$-approximation algorithm, a $2$-stable 2-approximation algorithm, and a $3$-stable $1.97$-approximation algorithm. - In $\mathbb{S}^1$ (where the underlying space is a circle) we prove that no SAS exists, even though an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in $\mathbb{R}^1$. - In $\mathbb{R}^2$, we also prove that no SAS exists, and we present a $O(1)$-stable $O(1)$-approximation algorithm., Comment: abstract shortened to meet the arxiv requirements

In this paper, we introduce an optimization problem posed by the Music Building Eindhoven (MBE) to deal with the economical consequences of the COVID-19 pandemic for theatre halls. We propose a model for maximizing the number of guests in a theatre hall that respects social distancing rules, and is based on trapezoid packings. Computational results show that up to 40% of the normal capacity can be used for a single show setting, and up to 70% in case artists opt for two consecutive performances per evening., Comment: 24 pages, 6 figures, submitted to INFORMS Journal on Applied Analytics

We introduce the Stackelberg kidney exchange problem. In this problem, an agent (e.g. a hospital or a national organization) has control over a number of incompatible patient-donor pairs whose patients are in need of a transplant. The agent has the opportunity to join a collaborative effort which aims to increase the maximum total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of patients under its control. Then, the question becomes which patients to submit to the collaborative effort. We show that, whenever we allow exchanges involving at most a fixed number $K \ge 3$ pairs, answering this question is $\Sigma_2^p$-complete. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time

We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequality. Each request needs to be served by a car, which means that a car must first visit the pick-up location of the request, and then visit the drop-off location of the request. Each car can serve two requests. One problem is to serve all requests with the minimum total travel time (called $\CS_{sum}$), and the other problem is to serve all requests with the minimum total latency (called $\CS_{lat}$). We also study the special case where the pick-up and drop-off location of a request coincide. We propose two basic algorithms, called the match and assign algorithm and the transportation algorithm. We show that the best of the resulting two solutions is a $ 2$-approximation for $\CS_{sum}$ (and a $7/5$-approximation for its special case), and a $5/3 $-approximation for $\CS_{lat}$ (and a $3/2$-approximation for its special case); these ratios are better than the ratios of the individual algorithms. Finally, we indicate how our algorithms can be applied to more general settings where each car can serve more than two requests, or where cars have distinct speeds.

Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm, and prove that this algorithm is a (3/2)-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem, and prove that, in one particular case, the algorithm is a (5/4)-approximation algorithm. Our analysis is tight in all cases except one.

For a given set of intervals on the real line, we consider the problem of ordering the intervals with the goal of minimizing an objective function that depends on the exposed interval pieces (that is, the pieces that are not covered by earlier intervals in the ordering). This problem is motivated by an application in molecular biology that concerns the determination of the structure of the backbone of a protein. We present polynomial-time algorithms for several natural special cases of the problem that cover the situation where the interval boundaries are agreeably ordered and the situation where the interval set is laminar. Also the bottleneck variant of the problem is shown to be solvable in polynomial time. Finally we prove that the general problem is NP-hard, and that the existence of a constant-factor-approximation algorithm is unlikely.