Hungarian Academy of Sciences (2007)
G Unter Rote, William Steiger, Cun-hui Zhang
Points P 1,..., Pn in the unit square define a convex n-chain if they are below y = x and, together with P 0 = (0, 0) and Pn+1 = (1, 1), they are in convex position. Under uniform probability, we...
Minimizing the Number of Tardy Jobs on a Single Machine with Batch Setup Times (1998)
Tu Graz Austria, Günter Rote, G Unter Rote, Gerhard J. Woeginger, Gerhard J. Woeginger
This paper investigates a single-machine sequencing problem where the jobs are divided into families, and where a setup time is incurred whenever there is a switch from a job in one family to a job...
Time Complexity and Linear-Time Approximation of the Ancient Two Machine Flow Shop (1997)
Tu Graz Austria, Günter Rote, G Unter Rote, Gerhard J. Woeginger, Gerhard J. Woeginger
We consider the scheduling problems F2 j j Cmax and F2 j no-wait j Cmax , i.e. makespan minimization in a two machine flow shop, with and without no wait in process. For both problems solution...
Curves with Increasing Chords (1993)
Diskrete Optimierung, Günter Rote, G Unter Rote
A curve has increasing chords if AD BC for any four points A; B; C; D lying on the curve in that order. The length of such a curve that connects two points at distance 1 is at most 2=3 in two...
Sequences With Subword Complexity 2n (1992)
We construct and discuss infinite 0-1-sequences which contain 2n different subwords of length n, for every n. 1 Introduction For an infinite word w = w 1 w 2 w 3 : : : over some finite alphabet, we...
The Convex-Hull-and-Line Traveling Salesman Problem: A Solvable Case (1992)
Diskrete Optimierung, Vladimir G. Deineko, Vladimir G. Deineko, René Van Dal, Ren'e Van Dal, Günter Rote, ...
We solve the special case of the Euclidean Traveling Salesman Problem where n \Gamma m cities lie on the boundary of the convex hull of all n cities, and the other m cities lie on a line segment...
The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions (1992)
The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is...
Sequences With Subword Complexity 2n (1992)
We construct and discuss in#nite 0-1-sequences which contain 2n di#erent subwords of length n, for every n. 1 Introduction For an in#nite word w = w 1 w 2 w 3 ::: over some #nite alphabet, we denote...