KLUEDO RSS Feed
Neueste Dokumente / Latest documents
https://kluedo.ub.unikl.de/index/index/
Sun, 09 Jul 2000 00:00:00 +0200
Sun, 09 Jul 2000 00:00:00 +0200

Some Complexity Results for kCardinality Minimum Cut Problems
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1140
Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the kcardinality minimum cut problem. Given an undirected edgeweighted graph the kcardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the kcardinality minimum st cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.
Maurizio Bruglieri; Matthias Ehrgott; Horst W. Hamacher
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1140
Thu, 07 Sep 2000 00:00:00 +0200

Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1132
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.
Horst W. Hamacher; Martine LabbĂ©; Stefan Nickel; Tim Sonneborn
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1132
Tue, 29 Aug 2000 00:00:00 +0200

Solving nonconvex planar location problems by finite dominating sets
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/973
It is wellknown that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and locationallocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead  for fixed epsilon  to polynomial approximation algorithms with accuracy epsilon for solving the general model considered in this paper.
Emilio Carrizosa; Horst W. Hamacher; Rolf Klein; Stefan Nickel
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/973
Fri, 18 Feb 2000 00:00:00 +0100