René van Bevern

activity

20092026

most citedParameterized complexity of machine scheduling: 15 open problems

66 citations · 457 across the 33 of their papers we have counts for

collaborators

Showing 2015 · cs.DSShow all

2 papers · 2 filters

cs.DS2015★ 28 cited

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack

René van Bevern, Rolf Niedermeier, Ondřej Suchý

We study the problem of non-preemptively scheduling $n$ jobs, each job $j$ with a release time $t_{j}$ , a deadline $d_{j}$ , and a processing time $p_{j}$ , on $m$ parallel identical machi…

cs.DS2015★ 17 cited

A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments

René van Bevern, Christian Komusiewicz, Manuel Sorge

We prove that any polynomial-time $α (n)$ -approximation algorithm for the $n$ -vertex metric asymmetric Traveling Salesperson Problem yields a polynomial-time $O (α (C))$ -approximation…