Luis Goddyn, Winfried Hochstättler
We consider the problem of reorienting an oriented matroid so that all its cocircuits are ‘as balanced as possible in ratio’. It is well known that any oriented matroid having no coloops has a...
Luis Goddyn, Winfried Hochstättler
We consider the problem of reorienting an oriented matroid so that all its cocircuits are ‘as balanced as possible in ratio’. It is well known that any oriented matroid having no coloops has a...
Antisymmetric flows in matroids (2008)
We present a seemingly new definition of flows and flow numbers for oriented matroids and prove that the flow number ΦL and the antisymmetric flow number ΦLas of an oriented matroid are bounded...
The flow lattice of oriented matroids (2008)
Winfried Hochstättler, Robert Nickel
Abstract. Recently Hochstättler and Neˇsetˇril introduced the flow lattice of an oriented matroid as generalization of the lattice of all integer flows of a digraph or more general a regular...
Matroid Polytopes On the Flow Lattice of Uniform Oriented (2008)
Grundlagen Der Informatik, Winfried Hochstättler, Robert Nickel, W. Hochstättler, ...
Recently Hochstättler and Neˇsetˇril introduced the flow lattice of an oriented matroid as generalization of the lattice of all integer flows of a digraph or more general a regular matroid. This...
David Schiess, Winfried Hochstättler, Robert Nickel
We introduce a new model for two-sided markets that generalizes sta- ble marriages as well as assignment games. Our model is a further gen- eralization of the model introduced by Eriksson and...
Winfried Hochstättler, Luis Goddyn
flow number introduced by Goddy, Tarsi and Zhang for an oriented matroid of rank r is bounded by 14r 2 ln r. We improve this bound by showing that any oriented matroid without a coloop admits a...
Lehrstuhl Für Mathematische, Grundlagen Der Informatik, Christian Hagemeier, Winfried Hochstättler
On a family of stars of maximal weight covering exactly k nodes
Flows On the Chromatic Number of an Oriented Matroid (2007)
Winfried Hochstättler, Robert Nickel, Winfried Hochstättler, Robert Nickel, ...
Winfried Hochstättler, Robert Nickel
We introduce a new maxflow-mincut (MFMC) property for oriented matroids and give necessary and sufficient conditions for a flow lattice of an oriented matroid or more general for an integer lattice...
Winfried Hochstättler, Robert Nickel
We define series/parallel/2-sum connection of two oriented matroids in terms of various axiom systems and an oriented modular join and sum operation by means of signed cocircuits and covectors. 1
Lehrstuhl für Diskrete Mathematik und Optimierung (2006)
Annabell Berger, Winfried Hochstättler, Lehrgebiet Mathematik, Annabell Berger, Winfried Hochstättler
Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors
Note on an auction procedure for matching games in polynomial time (2006)
Winfried Hochstättler, Hui Jin, Robert Nickel
We derive a polynomial time algorithm to compute a stable solution in a mixed matching market from an auction procedure as presented by Eriksson and Karlander [5]. As a special case we derive an...
Generalized colourings (matrix partitions) of cographs (2006)
Tomás Feder, Pavol Hell, Winfried Hochstättler
Ordinary colourings of cographs are well understood; we focus on more general colourings, known as matrix partitions. We show that all matrix partition problems for cographs admit polynomial time...
Winfried Hochstättler, Robert Nickel, Britta Peis, Proving Polynomiality
Signed graphs have been studied a lot during the last two decades. We address the vertex disjoint negative cycle packing problem posed by Zaslavsky [7, Problem II.A.1a]. Our aim is to find two vertex...
Winfried Hochstättler, Hui Jin, Robert Nickel, Lehrgebiet Mathematik, Lehrstuhl Diskrete, Mathematik Optimierung, ...
We present an algorithm that computes a stable matching in a common generalization of the marriage and the assignment game in O(n 4) time. 1
Balanced Signings of Oriented Matroids and Chromatic Number (2003)
Luis Goddyn, Petr Hlineny, Winfried Hochstättler
We consider te problem of reorienting an oriented matroid so that all its cocircuits...
Application of the Branch and Cut Method to the Vehicle Routing Problem (2002)
Ulrich Blasum, Winfried Hochstättler
The successful application of Branch and Cut methods to the TSP has drawn attention also to the polyhedral properties of the symmetric capacitated vehicle routing problem, which is the capacitated...
Steiner-Diagrams and k-Star-Hubs (2000)
Ulrich Blasum, Ulrich Blasum, Winfried Hochstättler, Winfried Hochstattler, Peter Oertel, Peter Oertel
In this report, we introduce and study two problems derived from reload problems in transport logistics. Given a transitive digraph G = (V; A; w) with non-negative edge-weights and a set of demand...
Application of the Branch and Cut Method to the Vehicle Routing Problem (2000)
Ulrich Blasum, Winfried Hochstättler
The successful application of Branch and Cut methods to the TSP has drawn attention also to the polyhedral properties of the symmetric capacitated vehicle routing problem, which is the capacitated...
The 5-Star-Hub-Problem is NP-complete (2000)
Keywords Star-hub, Vehicle Routing, Steiner Arborescence, Steiner Tree, Winfried Hochstättler, Winfried Hochstattler, ...
In this note we present a partial solution of the problems we left open in [1]. We show that the 5-Star-Hub-Problem is NP-complete. In [1] consider the following problem: Problem 1 (k-Star Hub...
Scheduling Trams in the Morning (1999)
Ulrich Blasum, Michael R. Bussieck, Winfried Hochstättler, Christoph Moll, Hans-Helmut Scheel, Thomas Winter
. In this note, we prove NP-completeness of the following problem: Given a set of trams of different types, which are stacked on sidings in their depot and an order in which trams of specified types...
Test Sets for Vertex Cover Problems (Extended Abstract) (1999)
Matthias Hayer, Winfried Hochstättler, W. Hochstattler
We describe the structure of the unique minimal test set T for a family of vertex cover problems. The set T corresponds to the Gröbner basis of the binomial ideal for the problem as described in...
Ulrich Blasum, Ulrich Blasum, Winfried Hochstättler, Winfried Hochstattler, Peter Oertel, Peter Oertel
In this report, we introduce and study the Steiner-diagram-problem. Given a transitive digraph G = (V; A; w) with non-negative edge-weights and a set of demand edges B, the objective is to find an...
Large Circuits in Binary Matroids of Large Cogirth: I (1998)
W. Hochstattler, B. Jackson, Winfried Hochstättler, Winfried Hochstattler, Bill Jackson, ...
Let F 7 denote the Fano matroid and e be a fixed element of F 7 . Let P (F 7 ; e) be the family of matroids obtained by taking the parallel connection of one or more copies of F 7 about e. Let M be a...
Bases of Cocycle Lattices and Submatrices of a Hadamard Matrix (1998)
W. Hochstattler, Martin Loebl, Zentrum Paralleles, Winfried Hochstättler, Martin Loebl
We study the lattice lat(M) of cocycles of a binary matroid M . By an isomorphism we show that such lattices are equivalent to lattices generated by the columns of proper submatrices of Sylvester...
Large Circuits in Binary Matroids of Large Cogirth: II (1998)
W. Hochstattler, B. Jackson, Winfried Hochstättler, Winfried Hochstattler, Bill Jackson, ...
Let F 7 denote the Fano matroid and M be a simple connected binary matroid such that every cocircuit of M has size at least d 3. We show that if M does not have an F 7 -minor, M 6= F 7 , and d = 2...
The Complexity of an Inverse Shortest Paths Problem (1998)
Sandor P. Fekete, Or P. Fekete, Winfried Hochstättler, Winfried Hochstattler, Stephan Kromberg, Stephan Kromberg, ...
In this paper we study the complexity of an Inverse Shortest Paths Problem (ISPP). We show that the problem is intractable even in very restricted cases. In particular, we prove that the ISPP is...
Linear Programming Duality and Morphisms (1998)
W. Hochstattler, Jarik Nesetril, W. Hochstattler, J. Nesetril, J. Nesetril, Zentrum Paralleles, ...
In this paper we investigate the class NP " co-NP (or the class of problems permitting a good characterisation) from the point of view of morphisms of oriented matroids. We prove several...
The nucleon of cooperative games and an algorithm for matching games (1997)
Ulrich Faigle, Sandor P. Fekete, Winfried Hochstättler, Walter Kern
The nucleon is introduced as a new allocation concept for non-negative cooperative n-person transferable utility games. The nucleon may be viewed as the multiplicative analogue of Schmeidler's...
About the Tic-Tac-Toe Matroid (1997)
W. Hochstattler, W. Hochstattler, Winfried Hochstättler
The purpose of this note is to make a problem, already mentioned in [3], more tangible. We introduce a matroid which has "the" combinatorial properties of algebraic matroids as derived in...
Tree Partitioning under Constraints Clustering for Vehicle Routing Problems (1997)
Anja Hamacher, Winfried Hochstättler, Christoph Moll
We present a dynamic programming algorithm for the following problem: Given a tree T = (V; E), a set of q non-negative integer weights w i : V ! N on the nodes, and a threshold R i ; i = 1; : : : ;...
About the Tic-Tac-Toe Matroid (1997)
W. Hochstattler, W. Hochstattler, Winfried Hochstättler
The purpose of this note is to make a problem, already mentioned in [3], more tangible. We introduce a matroid which has "the" combinatorial properties of algebraic matroids as derived in...
On approximately fair cost allocation in Euclidean TSP games (1996)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sandor P. Fekete, Winfried Hochstättler, ...
: We consider the problem of allocating the cost of an optimal traveling salesman tour in a fair way among the nodes visited; in particular, we focus on the case where the distance matrix of the...
Using Network-Flow Techniques to Solve an Optimization Problem From Surface-Physics (1996)
Ulrich Blasum, Winfried Hochstättler, W. Hochstattler, Heiko Rieger, Christoph Moll, H. Rieger, ...
this paper, that in the planar case the problem of minimizing the surface-energy can be reduced to the problem of finding a network-circulation, that minimizes a convex objective function. Preprint...
The Simulated Trading Heuristic for Solving Vehicle Routing Problems (1996)
A. Bachem, Winfried Hochstättler, A. Bachem, W. Hochstattler, W. Hochstattler, Martin Malich, ...
We present an improvement heuristic for vehicle routing problems. The heuristic finds complex customer interchanges to improve an initial solution. Our approach is modular, thus it is easily adjusted...
Scheduling Trams in the Morning is Hard (1996)
Ulrich Blasum, Michael R. Bussieck, Winfried Hochstättler, Christoph Moll, Hans-Helmut Scheel, Thomas Winter
In this note, we prove NP-completeness of the following problem: Given a set of trams of different types, which are stacked on sidings in their depot and an order in which trams of specified types...
Cycle bases for lattices of matroids with no Fano dual minor and their one-element extensions (1996)
W. Hochstattler, M. Laurent, Martin Loebl, Zentrum Paralleles, Rechnen Liens, Ecole Normale Sup'erieure, ...
In this paper we study the question of existence of a basis consisting only of cycles for the lattice Z(M) generated by the cycles of a binary matroid M. We show that, if M has no Fano dual minor,...
On approximately fair cost allocation in Euclidean TSP games (1996)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sándor P. Fekete, Winfried Hochstättler, ...
: We consider the problem of allocating the cost of an optimal traveling salesman tour in a fair way among the nodes visited; in particular, we focus on the case where the distance matrix of the...
Scheduling Trams in the Morning is Hard (1996)
Ulrich Blasum, Michael R. Bussieck, Winfried Hochstättler, Christoph Moll, Hans-Helmut Scheel, Thomas Winter
In this note, we prove NP-completeness of the following problem: Given a set of trams of different types, which are stacked on sidings in their depot and an order in which trams of specified types...
Menger's Theorem as Morphism Duality (1996)
W. Hochstattler, Jarik Nesetril, W. Hochstattler, J. Nesetril, J. Nesetril, Winfried Hochstättler, ...
The purpose of this note is to point out that Menger's Theorem in a quite natural way gives an example of a morphism duality. In this setting it is the simple equation (C k ; e) ! = 6! (C k+1 ;...
Farkas' Lemma and Morphism Duality (1996)
W. Hochstattler, Jarik Nesetril, W. Hochstattler, J. Nesetril, J. Nesetril, Winfried Hochstättler, ...
In this paper we investigate the class NP " co-NP (or the class of problems permitting a good characterization) from the point of view of morphisms of oriented matroids. We prove several...
On Bases Of Circuit Lattices (1995)
W. Hochstattler, W. Hochstattler, Martin Loebl, M. Loebl, Winfried Hochstättler, Martin Loebl
Our aim is to propose and study the following conjecture. There exists a set of cycles of each binary matroid B, which form a basis of the integer lattice generated by the circuits of B.
Oriented Matroids from Wild Spheres (1995)
In a recent article [5] we gave a lattice-theoretical characterization of oriented matroids in terms of the zero-map. In this paper we derive from that characterization a generalization of one...
A Lattice-Theoretical Characterization of Oriented Matroids (1995)
Winfried Hochstättler, Matroids Geometry, W. Hochstattler, W. Hochstattler
If P is the big face lattice of the covectors of an oriented matroid, it is well known that the zero map is a cover-preserving, order-reversing surjection onto the geometric lattice of the underlying...
A Pseudoconfiguration of Points without Adjoint (1995)
Winfried Hochstättler, W. Hochstattler, W. Hochstattler, W. Hochstattler, Stefan Kromberg, S. Kromberg, ...
We give an example of a simple oriented matroid D that admits an oriented adjoint. Already any adjoint of the underlying matroid D, however, does itself not admit an adjoint. D arises from the...
On The Complexity Of Testing Membership In The Core Of Min-Cost Spanning Tree Games (1994)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sandor P. Fekete, Winfried Hochstättler, ...
Let N = f1, ..., ng be a finite set of players and KN the complete graph on the node set N [ f0g. Assume that the edges of KN have nonnegative weights and associate with each coalition S ` N of...
Simulated Trading - A New Parallel Approach for Solving Vehicle Routing Problems (1994)
A. Bachem, Winfried Hochstättler, A. Bachem, W. Hochstattler, W. Hochstattler, Martin Malich, ...
Introduction Vehicle Routing Problems can be found in many variants (see [2] for a survey). As a generalization of the well-known Travelling Salesman Problem (TSP) it belongs to the class of...
A new Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon in the Plane (1994)
Winfried Hochstättler, W. Hochstattler, W. Hochstattler, W. Hochstattler, Stefan Kromberg, S. Kromberg, ...
The problem of determining the convex hull of a simple polygon has received a lot of attention in the early eighties. The first linear time algorithm for this task proposed by Sklansky in [S72] was...
Onion Skins in Oriented Matroids (1993)
W. Hochstattler, B. Gerards, B. Gerards, Winfried Hochstättler, Winfried Hochstattler
We generalize the following theorem to oriented matroids: Consider a polytope P and a facet F 0 of P , let H denote the hyperplanes spanned by F 0 . Let d denote the diameter of the coskeleton of P ....
Computational Experience with General Equilibrium Problems (1993)
Andreas Volmer, Winfried Hochstättler, Barthel Steckemetz, A. Volmer, A. Bachem, A. Bachem, ...
We report on computational experience with an implementation of three algorithms for the general economic equilibrium problem. As a result we get that the projection algorithm for variational...
On Pseudomodular Matroids and Adjoints (1993)
Marion Alfter, Winfried Hochstättler
There are two concepts of duality in combinatorial geometry. A set theoretical one, generalizing the structure of two orthocomplementary vector spaces and a lattice theoretical concept of an adjoint,...
A Note on the Weak Zone Theorem (1993)
Winfried Hochstättler, Winfried Hochstattler, Winfried Hochstattler
In a recent paper J. Matousek gave a simple proof of a weak form of the zone theorem which estimates the number of facets in the zone of a (Pseudo-)Hyperplane arrangement. In the Pseudo-Case he gave...
On Pseudomodular Matroids and Adjoints (1993)
Marion Alfter, Winfried Hochstättler
There are two concepts of duality in combinatorial geometry. A set theoretical one, generalizing the structure of two orthocomplementary vector spaces and a lattice theoretical concept of an adjoint,...
Hamiltonicity in graphs with few P 4 s (1993)
Winfried Hochstättler, G. Tinhofer, G. Tinhofer, W. Hochstattler, W. Hochstattler
In a recent series of articles R. Jamison and S. Olariu developed, starting from an extension of the notion of a cograph, a theory of the decomposition of graphs into P 4 -connected components. It...
A non-visiting path, nested cones and onion skins (1992)
W. Hochstattler, Winfried Hochstättler, Winfried Hochstattler
We prove that the skeleton graph of a cell of an oriented matroid is still connected, if we delete all nodes adjacent to one facet. As an application we solve a problem stated by T. Terlaky. 1...
Nested cones and onion skins (1992)
Winfried Hochstättler, Winfried Hochstattler, Winfried Hochstattler Cologne
We give a short geometric proof of a "nested cones" theorem answering a question asked by T. Terlaky in the Matroid Workshop of ARIDAM VII in the RUTCOR 1992. Exploiting polarity yields a...
Nested Cones and Onion Skins (1992)
Winfried Hochstättler, Winfried Hochstattler, Winfried Hochstattler Cologne
We give a short geometric proof of a "nested cones" theorem answering a question asked by T. Terlaky in the Matroid Workshop of ARIDAM VII in the RUTCOR 1992. Exploiting polarity yields a...
A Note on the Weak Zone Theorem (1992)
Winfried Hochstättler, Winfried Hochstattler, Winfried Hochstattler
In a recent paper J. Matousek gave a simple proof of a weak form of the zone theorem which estimates the number of facets in the zone of a (Pseudo-)Hyperplane arrangement. In the Pseudo-Case he gave...
Generating Convex Polyominoes at Random (1992)
Winfried Hochstattler Koln, Martin Loebl Praha, Christoph Moll Koln, Winfried Hochstättler, Martin Loebl, Christoph Moll
We give a new recursion formula for the number of convex polyominoes with fixed perimeter. From this we derive a bijection between an intervall of natural numbers and the polyominoes of given...
Sensitivity Analysis for General Equilibrium Problems (1992)
Achim Bachem, Winfried Hochstättler, Walter Wenzel
In this paper we give an elementary introduction into the theory of variational inequalities and their application to general equilibrium analysis. Furthermore we incorporate some results on...
A Non-Visiting Path, Nested Cones and Onion Skins (1992)
W. Hochstattler, Winfried Hochstättler, Winfried Hochstattler
We prove that the skeleton graph of a cell of an oriented matroid is still connected, if we delete all nodes adjacent to one facet. As an application we solve a problem stated by T. Terlaky.
Shellability of Oriented Matroids (1989)
Winfried Hochstättler, Winfried Hochstattler Cologne
In [Man82] A. Mandel proved that the maximal cells of an Oriented Matroid poset are B-shellable. Our result shows that the whole Oriented Matroid is shellable, too.
Winfried Hochstättler, Robert Nickel, David Schiess
We introduce a new model for two-sided markets that generalizes stable marriages as well as assignment games. Our model is a further generalization of the model introduced by Eriksson and Karlander...
On the Complexity of Testing Membership in the Core of Min-Cost Spanning Tree Games
Ulrich Faigle, Walter Kern, Winfried Hochstättler, Sándor P. Fekete
Let $N=\{ 1,...,n\} $ be a finite set of players and $K_{N}$ the complete graph on the node set $N\cup \{ 0\} $. Assume that the edges of $K_{N}$ have nonnegative weights and associate with each...