2020-10-30T11:09:15Zhttp://edoc.mpg.de/ac_ft_oai.ploai:edoc.mpg.de:2415932010-12-0387:936
On the Hadwiger's conjecture for graph products
Chandran, L. Sunil
Sivadasan, Naveen
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/241593
en
oai:edoc.mpg.de:5205892010-12-0387:936
BDDs in a Branch and Cut Framework
Becker, Bernd
Behle, Markus
Eisenbrand, Friedrich
Wimmer, Ralf
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/520589
urn:ISBN:3-540-25920-1
Nikoletseas, Sotiris: 4th International Workshop on Experimental and Efficient Algorithms (WEA'05), Springer, 452-463 (2005)
en
oai:edoc.mpg.de:5205942010-12-0387:936
Provisioning a Virtual Private Network Under the Presence of Non-Communicating Groups
Eisenbrand, Friedrich
Happ, Edda
expertsonly
Virtual private network design in the hose model deals with the
reservation of capacities in a weighted graph such
that the terminals in this network can communicate with one another. Each
terminal is equipped with an upper bound on the
amount of traffic that the terminal can send or receive. The task is
to install capacities at minimum cost and to compute paths for each
unordered terminal pair such that each valid traffic matrix can be
routed along those paths.
\noindent
In this paper we consider a variant of the virtual private
network design problem which generalizes the previously studied
symmetric and asymmetric case. In our model the terminal set is
partitioned into a number of groups, where terminals of each
group do not communicate with each other.
\noindent
Our main result is a 4.74 approximation algorithm for
this problem.
Springer
2006
Conference-Paper
http://edoc.mpg.de/520594
urn:ISBN:978-3-540-34375-2
Calamoneri, Tiziana; Finocchi, Irene; Italiano, Giuseppe F.: Algorithms and complexity : 6th Italian Conference, CIAC 2006, Springer, 105-114 (2006)
en
oai:edoc.mpg.de:5205982010-12-0387:936
0/1 vertex and facet enumeration with BDDs
Behle, Markus
Eisenbrand, Friedrich
expertsonly
SIAM
2007
Conference-Paper
http://edoc.mpg.de/520598
urn:ISBN:978-0-898716-28-3
Applegate, David; Brodal, Gerth Stolting; Panario, Daniel; Sedgewick, Robert: Proceedings of the ninth Workshop on Algorithm Engineering and Experiments (ALENEX'07), SIAM, 158-165 (2007)
en
oai:edoc.mpg.de:5205992010-12-0387:936
A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
Behle, Markus
Jünger, Michael
Liers, Frauke
expertsonly
Springer
2007
Conference-Paper
http://edoc.mpg.de/520599
urn:ISBN:978-3-540-72844-3
Demetrescu, Camil: 6th Workshop on Experimental Algorithms (WEA'07), Springer, 379-392 (2007)
en
oai:edoc.mpg.de:5206012010-12-0387:936
On Threshold BDDs and the Optimal Variable Ordering Problem
Behle, Markus
expertsonly
Springer
2007
Conference-Paper
http://edoc.mpg.de/520601
urn:ISBN:978-3-540-73555-7
Dress, Andreas; Xu, Yinfeng; Zhu, Binhai: First International Conference on Combinatorial Optimization and Applications (COCOA'07), Springer, 124-135 (2007)
en
oai:edoc.mpg.de:5206032011-07-2287:936
Binary Decision Diagrams and Integer Programming
Behle, Markus
expertsonly
In this work we show how Binary Decision Diagrams can be used as a powerful
tool for 0/1~Integer Programming and related polyhedral problems.
We develop an output-sensitive algorithm for building a threshold BDD, which
represents the feasible 0/1~solutions of a linear constraint, and give a
parallel \emph{and}-operation for threshold BDDs to build the BDD for a 0/1~IP.
In addition we construct a 0/1~IP for finding the optimal variable orderand
computing the variable ordering spectrum of a threshold BDD.
For the investigation of the polyhedral structure of a 0/1~IP
we show how BDDs can be applied to count or enumerate all 0/1~vertices of the
corresponding 0/1~polytope,
enumerate its facets, and find an optimal solution or count or enumerate all
optimal solutions to a linear objective function.
Furthermore we developed the freely available tool \texttt{azove}
which outperforms existing codes for the enumeration of 0/1~points.
Branch~\&~Cut is today's state-of-the-art method to solve 0/1~IPs. We present a
novel approach to generate valid
inequalities for 0/1~IPs which is based on BDDs.
We implemented our BDD based separation routine in a Branch~\&~Cut framework.
Our computational results show that our approach is well suited
to solve small but hard 0/1~IPs.
Universität des Saarlandes
2007
PhD-Thesis
http://edoc.mpg.de/520603
en
oai:edoc.mpg.de:5206052010-12-0387:936
Packing a Trunk - Now with a Twist!
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Reichel, Joachim
Schömer, Elmar
expertsonly
In an industry project with a German car manufacturer we
are faced with the challenge of placing a maximum number of
uniform rigid rectangular boxes in the interior of a car
trunk. The problem is of practical importance due to a
European industry norm which requires car manufacturers
to state the trunk volume according to this measure.
No really satisfactory automated solution for this problem has been
known in the past. In spite of its NP hardness, combinatorial
optimization techniques, which consider only grid-aligned placements,
produce solutions which are very close to the one achievable by a
human expert in several hours of tedious work. The remaining gap is
mostly due to the constraints imposed by the chosen grid.
In this paper we present a new approach which combines the grid-based
combinatorial method with \emph{Simulated Annealing} on a continuous
model. This allows us to explore arbitrary orientations and placements
of boxes, hence closing the gap even further, and -- in some cases --
even surpass the manual expert solution.
The implemented software system allows our industrial partner to
incorporate the trunk volume in a very early stage of the car design
process without relying on a repeated and cumbersome manual evaluation
of the volume.
2007
Article
http://edoc.mpg.de/520605
info:doi/10.1142/S021819590700246X
International Journal of Computational Geometry and Applications, v.17, 505-527 (2007)
en
oai:edoc.mpg.de:5206182010-12-0387:936
Similarity Assessment for Generalizied Cases by Optimization Methods
Mougouie, Babak
Bergmann, Ralph
expertsonly
Generalized cases are cases that cover a subspace rather than a
point in the problem-solution space. Generalized cases can be
represented by a set of constraints over the case attributes. For
such representations, the similarity assessment between a point
query and generalized cases is a difficult problem that is
addressed in this paper. The task is to find the distance (or the
related similarity) between the point query and the closest point
of the area covered by the generalized cases, with respect to some
given similarity measure. We formulate this problem as a
mathematical optimization problem and we propose a new cutting
plane method which enables us to rank generalized cases according
to their distance to the query.
Springer
This work is subject to copyright. All rights are reserved,
whether the whole or part of the material is concerned,
specifically the rights of translation, reprinting, re-use of
illustrations, recitation, broadcasting, reproduction on
microfilms or in any other way, and storage in data banks.
Duplication of this publication or parts thereof is permitted
only under the provisions of the German Copyright Law of
September 9, 1965, in its current prosecution under the
German Copyright Law.
2002
Conference-Paper
http://edoc.mpg.de/520618
urn:ISBN:3-540-44109-3/0302-9743
Craw, Susan; Preece, Alun: Advances in Case-Based Reasoning, 6th European Conference, ECCBR 2002; proceedings, Springer, 249-263 (2002)
en