2 citations · 2 across the 2 of their papers we have counts for
6 papers
Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time
Philippe Baptiste, Marek Chrobak, Christoph Durr +1
We study the problem of preemptive scheduling of n equal-length jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time.…
Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
Philippe Baptiste, Marek Chrobak, Christoph Durr +2
We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput, which…
Reconstructing hv-Convex Polyominoes from Orthogonal Projections
Christoph Durr, Marek Chrobak
Tomography is the area of reconstructing objects from projections. Here we wish to reconstruct a set of cells in a two dimensional grid, given the number of cells in every row and…
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms
Christoph Durr, Marek Chrobak
We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dime…
A decision procedure for well-formed linear quantum cellular automata
Christoph Durr, Huong LeThanh, Miklos Santha
In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since i…
Tiling with bars under tomographic constraints
Christoph Durr, Eric Goles, Ivan Rapaport +1
We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We prese…