KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 08 Nov 2017 16:03:14 +0100Wed, 08 Nov 2017 16:03:14 +0100An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5049
Let \(a_1,\dots,a_m\) be i.i .d. vectors uniform on the unit sphere in \(\mathbb{R}^n\), \(m\ge n\ge3\) and let \(X\):= {\(x \in \mathbb{R}^n \mid a ^T_i x\leq 1\)} be the random polyhedron generated by. Furthermore, for linearly independent vectors \(u\), \(\bar u\) in \(\mathbb{R}^n\), let \(S_{u, \bar u}(X)\) be the number of shadow vertices of \(X\) in \(span (u, \bar u\)). The paper provides an asymptotic expansion of the expectation value \(E (S_{u, \bar u})\) for fixed \(n\) and \(m\to\infty\). The first terms of the expansion are given explicitly. Our investigation of \(E (S_{u, \bar u})\) is closely connected to Borgwardt's probabilistic analysis of the shadow vertex algorithm - a parametric variant of the simplex algorithm. We obtain an improved asymptotic upper bound for the number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5049Wed, 08 Nov 2017 16:03:14 +0100A Note on Approximation Algorithms for the Multicriteria \(\Delta\)-TSP
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5031
The Tree and Christofides heuristic are weil known 1- and \(\frac{1} {2}\)- approximate algorithms for the \(\Delta\)-TSP. In this note their performance for the multicriteria case is described, depending on the norm in \(\mathbb{R}^Q\) in case of \(Q\) criteria.Matthias Ehrgott; Alexander Feldmannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5031Mon, 06 Nov 2017 11:45:28 +0100Mathematik als Vehikel der Philosophie und Weltanschauung
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4887
Knut Radbruchreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4887Thu, 19 Oct 2017 10:05:34 +0200On Matroids with Multiple Objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4850
In this paper we investigate two optimization problems for matroids with multiple objective functions, namely finding the pareto set and the max-ordering problem which conists in finding a basis such that the largest objective value is minimal. We prove that the decision versions of both problems are NP-complete. A solution procedure for the max-ordering problem is presented and a result on the relation of the solution sets of the two problems is given. The main results are a characterization of pareto bases by a basis exchange property and finally a connectivity result for proper pareto solutions.Matthias Ehrgottreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4850Mon, 16 Oct 2017 09:14:56 +0200Lexicographic Max-Ordering - A Solution Concept for Multicriteria Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4849
In this paper we will introduce the concept of lexicographic max-ordering solutions for multicriteria combinatorial optimization problems. Section 1 provides the basic notions of
multicriteria combinatorial optimization and the definition of lexicographic max-ordering solutions. In Section 2 we will show that lexicographic max-ordering solutions are pareto optimal as well as max-ordering optimal solutions. Furthermore lexicographic max-ordering solutions can be used to characterize the set of pareto solutions. Further properties of lexicographic max-ordering solutions are given. Section 3 will be devoted to algorithms. We give a polynomial time algorithm for the two criteria case where one criterion is a sum and one is a bottleneck objective function, provided that the one criterion sum problem is solvable in polynomial time. For bottleneck functions an algorithm for the general case of Q criteria is presented.Matthias Ehrgottreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4849Mon, 16 Oct 2017 08:57:51 +0200Connectedness of Efficient Solutions in Multiple Criteria Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4844
In multiple criteria optimization an important research topic is the topological structure of the set \( X_e \) of efficient solutions. Of major interest is the connectedness of \( X_e \), since it would allow the determination of \( X_e \) without considering non-efficient solutions in the
process. We review general results on the subject,including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.Matthias Ehrgott; Kathrin Klamrothreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4844Mon, 16 Oct 2017 08:41:05 +0200Existence of twistor spaces of algebraic dimension two over the connected sum o
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/809
Frédéric Campana; Bernd Kreußlerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/809Mon, 03 Apr 2000 00:00:00 +0200Moishezon twistor spaces without effective divisors of degree one
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/811
Bernd Kreußlerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/811Mon, 03 Apr 2000 00:00:00 +0200Symmetry properties of average densities and tangent measure distributions of measures on the line
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/818
Answering a question by Bedford and Fisher we show that for every Radon measure on the line with positive and finite lower and upper densities the one-sided average densities always agree with one half of the circular average densities at almost every point. We infer this result from a more general formula, which involves the notion of a tangent measure distribution introduced by Bandt and Graf. This formula shows that the tangent measure distributions are Palm distributions and define self-similar random measures in the sense of U. Zähle.Peter Mörterspreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/818Mon, 03 Apr 2000 00:00:00 +0200