The second author acknowledges partial financial support from the `Christian Doppler Labor (2007)
Svatopluk Poljak, Franz Rendl, Diskrete Optimierung
We study the problem of finding the minimum bisection of a graph into two parts of prescribed sizes. We formulate two lower bounds on the problem by relaxing node- and edge- incidence vectors of...
Diskrete Optimierung, A C Ela, Thomas Korimort, Rainer Burkard, Eranda C Ela
An interior point approach for weighted bipartite matching
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Tiziana Fortuna, Tiziana Fortuna, ...
An event-driven model for chemical batch processes
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Hans Kellerer, Hans Kellerer, Thomas Tautenhahn, Thomas Tautenhahn, ...
We consider the problem of scheduling n jobs that are released over time on a single machine in order to minimize the total flow time. This problem is well-known to be NPcomplete, and the best...
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Gunter Rote, Triangulations Intersect Nicely, Oswin Aichholzer, Oswin Aichholzer, ...
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Volker Kaibel, Gunter Rote, Bericht Nr, Endgultige Fassung Janner
We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d \Gamma 1)! + 2(d \Gamma 1) (which is the best one currently known for small...
Kontrolle Projektbereich, Diskrete Optimierung, Vladimir G. Deineko, Dedicated Dimitry, A. Suprunenko, ...
We introduce the concept of long-chord-free and fence-free tours in connection with the travelling salesman problem (TSP). These tours form a non-trivial subset of the cyclic permutations. We prove...
ON PLANARITY AND COLORABILITY OF CIRCULANT GRAPHS (2007)
Diskrete Optimierung, Clemens Heuberger, Clemens Heuberger
Abstract. For given postive integers n; a1; : : : ; am we consider the undirected circulant graph G = (V; E) with vertices V = f0; : : : ; n 1g and edges E = f[i; j] : i j a k (mod n) for some 1 k...
ON HAMILTONIAN TOEPLITZ GRAPHS (2007)
Diskrete Optimierung, Clemens Heuberger, Clemens Heuberger
und
UET---Scheduling with Chain-type Precedence Constraints (2007)
Diskrete Optimierung, Jansen Woeginger Yu, Klaus Jansen, Gerhard J. Woeginger, Zhongliang Yu
UET-scheduling with chain-type precedence constraints
Diskrete Optimierung, Stefan E. Karisch, Eranda C Ela, Jens Clausen, Jens Clausen, Torben Espersen, ...
A dual framework for lower bounds of the quadratic assignment problem based on linearization
Max Algebra and the Linear Assignment Problem (2003)
Diskrete Optimierung, Peter Butkovic, Max Algebra, Rainer E. Burkard
Max-algebra, where the classical arithmetic operations of addition and multiplication are replaced by a b := max(a; b) and b := a + b oers an attractive way for modelling discrete event systems and...
Bottleneck Capacity Expansion Problems With General Budget Constraints (2000)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Bettina Klinz, Bettina Klinz, Jianzhong Zhang, ...
This paper presents a unified approach for bottleneck capacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set E, a family F of feasible...
Selected Topics on Assignment Problems (1999)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard
. We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignment problems and applications, multidimensional assignment problems, quadratic...
2-Medians in Networks with Pos/Neg Weights (1999)
Diskrete Optimierung, Eranda Çela, Rainer E. Burkard, Bericht Nr. Juli, Rainer E. Burkard, Helidon Dollani
This paper deals with facility location problems with pos/neg weights in trees. We consider two different objective functions which model two different ways to handle obnoxious facilities. If we...
The Obnoxious Center Problem on a Tree (1998)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Helidon Dollani, Helidon Dollani, Yixun Lin, ...
The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We...
Linear Assignment Problems and Extensions (1998)
Diskrete Optimierung, Eranda Çela, Rainer E. Burkard, A C� Ela, Bericht Nr. Juni, Rainer E. Burkard
This paper aims at describing the state of the art on linear assignment problems (LAPs). Besides sum LAPs it discusses also problems with other objective functions like the bottleneck LAP, the...
The Quadratic Assignment Problem (1998)
Diskrete Optimierung, Eranda Çela, Rainer E. Burkard, A C� Ela, Bericht Nr. Mai, Rainer E. Burkard, ...
This paper aims at describing the state of the art on quadratic assignment problems (QAPs). It discusses the most important developments in all aspects of the QAP such as linearizations, QAP...
On the TSP with a Relaxed General Distribution Matrix (1998)
Diskrete Optimierung, Rainer E. Burkard, Vladimir G. Deineko, Vladimir G. Deineko
. We show that the traveling salesman problem with a symmetric relaxed Monge matrix as distance matrix is pyramidally solvable and can thus be solved by dynamic programming. Furthermore, we present a...
Volume Maximization and Orthoconvex Approximation of Orthogons (1998)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Mikalai M. Miatselski, Mikalai M. Miatselski
Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks...
Rounding Strategies for Mixed Integer Programs Arising from Chemical Production Planning (1997)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Michael Kocher, Michael Kocher, Rüdiger Rudolf, ...
: In this paper we consider problems which stem from production planning processes in the chemical industry. Many of these problems may be formulated as mixed integer linear programs. Since it is a...
Diskrete Optimierung, R.E. Burkard, V. M. Demidenko, R. Rudolf, Rainer E. Burkard, Vitali M. Demidenko, ...
: In this paper we develop a general method to obtain special cases of the (asymmetric) travelling salesman problem with a fixed optimal tour. This is done by specifying sufficient conditions on the...
Efficiently Solvable Special Cases of Hard Combinatorial Optimization (1997)
Diskrete Optimierung, Bericht Nr. Februar, Rainer E. Burkard, Rainer E. Burkard
We survey some recent advances in the field of polynomially solvable special cases of hard combinatorial optimization problems like the travelling salesman problem, quadratic assignment problems and...
On-line Waste Management in a. . . (1996)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Ulrich Pferschy, Ulrich Pferschy, ...
In this paper we present a case study of a waste--water treatment procedure for a zinc galvanization unit of a metal--processing company. During the process of galvanization several types of...
Three-Clustering of Points in the Plane (1996)
Diskrete Optimierung, Günter Rote, Johann Hagauer, Johann Hagauer
Given n points in the plane, we partition them into three classes such that the maximum distance between two points in the same class is minimized. The algorithm takes O(n 2 log 2 n) time.
Spanning Trees and Shortest Paths in Monge Graphs (1996)
Tibor Dudás, Diskrete Optimierung, Rüdiger Rudolf, Tibor Dud As
. In this paper the research on the influence of Monge structures on combinatorial optimization problems is continued. Precisely, we investigate three problems on Monge graphs, i.e. complete,...
A Note on Kalmanson Matrices (1996)
Diskrete Optimierung, Vitali M. Demidenko, Vitali M. Demidenko, Rüdiger Rudolf, Rudiger Rudolf
: In this note we derive an additive characterization of Kalmanson matrices by investigating the cone of this matrix class. With the help of this characterization, a simple proof for a result...
An Interior-Point Method for Semidefinite Programming (1996)
Diskrete Optimierung, Christoph Helmberg, Christoph Helmberg, Franz Rendl, Franz Rendl, Robert J. Vanderbei, ...
We propose a new interior point based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices....
Constant-Level Greedy Triangulations Approximate the MWT Well (1995)
Diskrete Optimierung, O. Aichholzer, F. Aurenhammer, G. Rote, Oswin Aichholzer, ...
The well-known greedy triangulation GT (S) of a finite point set S is obtained by inserting compatible edges in increasing length order, where an edge is compatible if it does not cross previously...
Lower Bounds for the Quadratic Assignment Problem via Triangle Decompositions (1995)
Diskrete Optimierung, Stefan E. Karisch, Stefan E. Karisch, Franz Rendl, Franz Rendl
We consider transformations of the (metric) Quadratic Assignment Problem (QAP), that exploit the metric structure of a given instance. We show in particular, how the structural properties of...
The Travelling Salesman Problem on Permuted Monge Matrices (1995)
Diskrete Optimierung, Vladimir G. Deineko, Rainer E. Burkard, Rainer E. Burkard, Gerhard J. Woeginger, ...
. We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar...
Heuristics for Biquadratic Assignment Problems and their Computational Comparison (1995)
Diskrete Optimierung, E. Çela, Rainer E. Burkard, Rainer E. Burkard
The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). As for any hard optimization problem also for BiQAP, a reasonable effort to cope with the...
Hamiltonian Cycles in Circulant Digraphs with Two Stripes (1995)
Diskrete Optimierung, Qi Fan Yang, Eranda Çela, Yang Rainer, Rainer E. Burkard, Qi Fan Yang, ...
. The Circulant Travelling Salesman Problem (CTSP) is the problem of finding a minimum weight Hamiltonian cycle in a weighted graph with circulant distance matrix. The computational complexity of...
Sequencing Jobs that Require Common Resources on a Single Machine: A Solvable Case of the TSP (1995)
Diskrete Optimierung, Jack A. A, Veen Gerhard, Gerhard J. Woeginger, Gerhard J. Woeginger, ...
In this paper a one-machine scheduling model is analyzed where n different jobs are classified into K groups depending on which additional resource they require. The changeover time from one job to...
Perspectives of Monge Properties in Optimization (1995)
Diskrete Optimierung, Rüdiger Rudolf, Rainer E. Burkard, Rainer E. Burkard, Bettina Klinz, Bettina Klinz
An m × n matrix C is called Monge matrix if c ij + c rs c is + c rj for all 1 i ! r m, 1 j ! s n. In this paper we present a survey on Monge matrices and related Monge properties and their...
A Unified Approach to Simple Special Cases of Extremal Permutation Problems (1995)
Diskrete Optimierung, Eranda Çela, Rainer E. Burkard, Rainer E. Burkard, Vitaly M. Demidenko, Nikolai N. Metelski, ...
Extremal permutation problems are combinatorial problems where an objective function has to be optimized over a set of permutations (as e.g. assignment problems and the travelling salesman problem)....
Three Easy Special Cases of the Euclidean Travelling Salesman (1995)
Diskrete Optimierung, Rüdiger Rudolf, Jack A. A, Veen Gerhard, ...
. It is known that in case the distance matrix in the Travelling Salesman Problem (TSP) fulfills certain combinatorial conditions (e.g. the Demidenko conditions, the Kalmanson conditions or the...
Webs, Iteration Groups, and Equivalent Changes in Probabilities (1994)
János Aczél, Diskrete Optimierung, Günter Rote, Jens Schwaiger, Jens Schwaiger
Yew-Kwang Ng #Quart. Appl. Math. 49 #1991#, 289#301# listed several #reasonable properties " for equivalentchanges of probabilities and other proportions. He produced a family of functions...
Webs, Iteration Groups, and Equivalent Changes in Probabilities (1994)
János Aczel, Diskrete Optimierung, Günter Rote, Jens Schwaiger, Jens Schwaiger
Yew-Kwang Ng (Quart. Appl. Math. 49 (1991), 289--301) listed several "reasonable properties " for equivalent changes of probabilities and other proportions. He produced a family of...
A Note on the Maximum of a certain Bilinear Form (1994)
Eranda Cela, Gerhard J. Woeginger, Diskrete Optimierung
. In this note a generalization of a result by Hardy, Littlewood and P'olya (1926) is derived on computing the maximum of a certain bilinear form. The proof is elementary. 1 Introduction For a...
Node and Edge Relaxations of the Max-Cut Problem (1994)
Diskrete Optimierung, Svatopluk Poljak, Svatopluk Poljak, Franz Rendl, Franz Rendl
We study an upper bound on the max-cut problem defined via a relaxation of the discrete problem to a continuous nonlinear convex problem, which can be solved efficiently. We demonstrate how far the...
On the Recognition of Permuted Supnick and Incomplete Monge Matrices (1994)
Diskrete Optimierung, Monge Matrices, Vladimir Deineko, Vladimir Deineko, Rüdiger Rudolf, Rudiger Rudolf, ...
. Incomplete Monge matrices are a generalization of standard Monge matrices: the values of some entries are not specified and the Monge property only must hold for all specified entries. We derive...
Sometimes Travelling is Easy: The Master Tour Problem (1994)
Diskrete Optimierung, Rüdiger Rudolf, Vladimir G. Deineko, Vladimir G. Deineko, Gerhard J. Woeginger, Gerhard J. Woeginger
. In 1975, Kalmanson proved that in case the distance matrix in the Travelling Salesman Problem (TSP) fulfills certain combinatorial conditions (nowadays called the Kalmanson conditions) then the TSP...
A Minimax Assignment Problem in Treelike Communication Networks (1994)
Diskrete Optimierung, Eranda Çela, Rainer E. Burkard, Rainer E. Burkard, Gerhard J. Woeginger
. A given system of communication centres C 1 ; C 2 ; : : : ; C n has to be embedded into a given undirected network N . The centres exchange messages at given rates per time unit through a selected...
Cost Optimization for the Slitting of Core Laminations for Power Transformers (1994)
Diskrete Optimierung, Core Laminations, Power Transformers, A. Gerstl, Alois Gerstl, Elin Transformatoren Gesmbh, ...
The successful realization of a project for slitting core laminations for power transformers under minimizing costs is presented. The production of the core of power transformers requires great...
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...
A Spectral Approach to Bandwidth and Separator Problems in Graphs (1993)
Diskrete Optimierung, Christoph Helmberg, Christoph Helmberg, Bojan Mohar, Bojan Mohar, Svatopluk Poljak, ...
Lower bounds on the bandwidth, the size of a vertex separator of general undirected graphs, and the largest common subgraph of two undirected (weighted) graphs are obtained. The bounds are based on a...
Monge Matrices Make Maximization Manageable (1993)
Diskrete Optimierung, Rüdiger Rudolf, Ulrich Pferschy, Ulrich Pferschy, Rudiger Rudolf, Gerhard J. Woeginger, ...
. We continue the research on the effects of Monge structures in the area of combinatorial optimization. We show that three optimization problems become easy if the underlying cost matrix fulfills...
Cutting Aluminium Coils with High Length Variabilities (1993)
Diskrete Optimierung, Cutting Aluminium Coils, High Length Variabilities, Christoph Helmberg, Christoph Helmberg
A case study of a cutting stock problem in an aluminium mill is presented. Orders have release dates, due dates, a total length and may be delivered in any number of coils within rather large length...
Some Geometric Clustering Problems (1993)
Diskrete Optimierung, Rüdiger Rudolf, Ulrich Pferschy, Ulrich Pferschy, Rudiger Rudolf, Gerhard J. Woeginger, ...
This paper investigates the computational complexity of several clustering problems with special objective functions for point sets in the Euclidean plane. Our strongest negative result is that...
A General Approach To Avoiding Two by Two Submatrices (1993)
Diskrete Optimierung, Rüdiger Rudolf, Vladimir Deineko, Vladimir Deineko, Rudiger Rudolf, Gerhard J. Woeginger, ...
A matrix C is said to avoid a set F of matrices, if no matrix of F can be obtained by deleting some rows and columns of C. In this paper we consider the decision problem whether the rows and columns...
On Monge Sequences in d-Dimensional Arrays (1993)
Diskrete Optimierung, Rüdiger Rudolf, Rudiger Rudolf
. Let C be an n \Theta m matrix. Then the sequence S := ((i 1 ; j 1 ); (i 2 ; j 2 ); : : : ; (i nm ; j nm )) of pairs of indices is called a Monge sequence with respect to the given matrix C if and...
Diskrete Optimierung, Stefan E. Karisch, Mike Power, S. E. Karisch, M. Power
The paper argues that modelling provides a convenient and cost effective means of characterizing and predicting the behaviour of environmental systems disturbed by man. A series of modelling criteria...
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...