20 citations · 62 across the 20 of their papers we have counts for
14 papers · 1 filter
Total Completion Time Scheduling Under Scenarios
Thomas Bosman, Martijn van Ee, Ekin Ergen +4
Scheduling jobs with given processing times on identical parallel machines so as to minimize their total completion time is one of the most basic scheduling problems. We study inte…
Elastic-Degenerate String Matching with 1 Error
Giulia Bernardini, Estéban Gabory, Solon P. Pissis +3
An elastic-degenerate string is a sequence of finite sets of strings of total length , introduced to represent a set of related DNA sequences, also known as a pangenome. The…
A Universal Error Measure for Input Predictions Applied to Online Graph Problems
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela +3
We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a ge…
String Sanitization Under Edit Distance: Improved and Generalized
Takuya Mieno, Solon P. Pissis, Leen Stougie +1
Let be a string of length over an alphabet , be a positive integer, and be a set of length- substrings of . The ETFS problem asks us to construct…
Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
Mark Jones, Steven Kelk, Leen Stougie
Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results a…
Optimal Algorithms for Scheduling under Time-of-Use Tariffs
Lin Chen, Nicole Megow, Roman Rischke +2
We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition…
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Neil Olver, Frans Schalekamp, Suzanne van der Ster +2
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades,…
A Fully Polynomial Time Approximation Scheme for Packing While Traveling
Frank Neumann, Sergey Polyakovskiy, Martin Skutella +2
Understanding the interactions between different combinatorial optimisation problems in real-world applications is a challenging task. Recently, the traveling thief problem (TTP),…
On unrooted and root-uncertain variants of several well-known phylogenetic network problems
Leo van Iersel, Steven Kelk, Georgios Stamoulis +2
The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegre…
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades,…
Scheduling over Scenarios on Two Machines
Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp +4
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scena…
Split Scheduling with Uniform Setup Times
Frans Schalekamp, Rene Sitters, Suzanne van der Ster +3
We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job req…
The traveling salesman problem on cubic and subcubic graphs
Sylvia Boyd, René Sitters, Suzanne van der Ster +1
We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relati…
Minimizing Flow Time in the Wireless Gathering Problem
Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela +1
We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data pa…