Publications (12)
To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
Sander Borst, Moritz Venzin
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For -node graphs with at most non-zero node-weights, and at mo…
On the Integrality Gap of Binary Integer Programs with Gaussian Data
Sander Borst, Daniel Dadush, Sophie Huiberts +1
For a binary integer program (IP) , where and have independent Gaussian…
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Sander Borst, Marek Eliáš, Moritz Venzin
We propose a -competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous b…
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
Sander Borst, Leo van Iersel, Mark Jones +1
We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm fo…
Majorizing Measures for the Optimizer
Sander Borst, Daniel Dadush, Neil Olver +1
The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochas…
Improved Online Load Balancing in the Two-Norm
Sander Borst, Danish Kashaev
We study the online load balancing problem on unrelated machines, with the objective of minimizing the square of the norm of the loads on the machines. The greedy algorith…