Publications by Thomas Rothvoss

Related publications (18)

An Improved LP-based Approximation for Steiner Tree

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...

EPFL2009

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

Network Design via Core Detouring for Problems Without a Core

Thomas Rothvoss

Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvo\ ...

Springer2010

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Pricing on Paths: A PTAS for the Highway Problem

Thomas Rothvoss

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the assoc ...

2011

Diameter of Polyhedra: Limits of Abstraction

Friedrich Eisenbrand, Thomas Rothvoss, Nicolai Hähnle

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to ...

2009

Connected facility location via random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...

2010

On the Complexity of the Asymmetric VPN Problem

Thomas Rothvoss, Laura Sanità

We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (VPN) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2 OPT and that a tree so ...

Springer2009

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk

Thomas Rothvoss, Laura Sanità

The virtual private network problem (VPN) models scenarios in which traffic is uncertain or rapidly changing. The goal is supporting at minimum cost a given family of traffic matrices, which are implicitly given by upper bounds on the ingoing and outgoing ...

2011

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

Thomas Rothvoss

We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k it yields solutions with at most (3/2 + 1/k)*OPT+9k many processors, thus it gives a ...

Springer2011

EDF-schedulability of synchronous periodic task systems is coNP-hard

Friedrich Eisenbrand, Thomas Rothvoss

In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...

2010

Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

Thomas Rothvoss

This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm. The quantitative metric used in this comparison is the processor speedup factor, equivalent to the factor by ...

2009

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Thomas Rothvoss

We introduce the "First Fit Matching Periods" algorithm for static-priority multiprocessor scheduling of periodic tasks with implicit deadlines and show that it yields asymptotically optimal processor assignments if utilization values are chosen uniformly ...

Springer2009

Optimal Selection of Customers for a Last-Minute Offer

Thomas Rothvoss

We analyze a short-term revenue optimization problem involving the targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the offer will be ...

2010

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa2011

Static-priority Real-time Scheduling: Response Time Computation is NP-hard

Friedrich Eisenbrand, Thomas Rothvoss

IEEE Computer Society2008

Convexly independent subsets of the Minkowski sum of planar point sets

János Pach, Friedrich Eisenbrand, Thomas Rothvoss

Let P and Q be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum S ⊆ P⊕Q which consist of convex independent points. We show that, if P and Q contain at most n points, then |S| = O(n^(4/3) ...

American Mathematical Society2008