FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:   || 2 | 3 | 4 | 5 |   ...   | 16 |

«Algorithmic Approaches for Solving Hard Problems: Approximation and Complexity A dissertation submitted to the Swiss Federal Institute of Technology ...»

-- [ Page 1 ] --

Diss. ETH No. 18748

Algorithmic Approaches for Solving Hard Problems:

Approximation and Complexity

A dissertation submitted to the

Swiss Federal Institute of Technology Zurich (ETH)

for the degree of

Doctor of Sciences

presented by

Tobias M¨mke


Dipl.-Inform. Rheinisch-Westf¨lische Technische Hochschule Aachen


Born on September 24, 1979

citizen of Germany

accepted on the recommendation of

Prof. Dr. J. Hromkoviˇ, examiner


Prof. Dr. P. Widmayer, co-examiner Prof. Dr. P. Rossmanith, co-examiner iii Zusammenfassung In dieser Dissertation behandeln wir Methoden zum L¨sen schwerer Probleme, die uber die o ¨ klassische Approximation hinausgehen. Diese Methoden sind aus zwei Gr¨nden n¨tzlich. Zum u u einen bieten sie neue M¨glichkeiten, L¨sungen zu algorithmischen Problemen zu finden. Zum o o anderen bilden sie die Grundlage f¨r neue Techniken zur Analyse der Frage, welche Faktoren u ein Problem NP-schwer machen bzw. weshalb Probleme schwer zu approximieren sind. Im gleichen Kontext schließen wir diese Dissertation mit komplexit¨tstheoretischen Resultaten a ab.

Unser erstes Resultat besch¨ftigt sich mit der Struktur von Eingabeinstanzen f¨r das a u Traveling-Salesman-Problem in metrischen Graphen. Das Ziel hierbei ist es, einen Kreis mit minimalen Kosten zu finden, der jeden Knoten des Graphen genau ein Mal besucht. Der Christofides-Algorithmus, der schon im Jahr 1976 ver¨ffentlicht wurde, ist 1.5-approximativ o und damit der bislang beste Approximationsalgorithmus f¨r dieses Problem. F¨r unsere u u Analyse betrachten wir zudem den bislang besten Algorithmus f¨r ein verwandtes Problem, u das Hamilton-Pfad-Problem in metrischen Graphen mit vorgegebenen Endknoten. Dieser Algorithmus stammt von Hoogeveen und ist 5/3-approximativ. Wir charakterisieren schwere Eingaben

–  –  –

Abstract In this dissertation, we study approaches beyond classical approximation for solving hard problems. The use of these approaches is twofold. On the one hand, they establish new computational possibilities for finding solutions to hard problems. On the other hand, they provide techniques to analyze the reason why certain problems are NP -hard or hard to approximate.

Accordingly, the main focus of this thesis is the analysis of computational hardness, approximability, and parameters that influence the hardness of problems. In the same context, we conclude the thesis with complexity-theoretic results.

Our first result concerns the structure of hard input instances for the traveling salesman problem in metric graphs. The goal of the problem is to find a minimum cost cycle that contains each vertex of the graph exactly once. Christofides’ algorithm, which was first published in 1976 and achieves an approximation ratio of 1.5, is to date the best approximation algorithm for this problem. For our analysis, we also consider the best up-to-date algorithm for a related problem, the Hamiltonian path problem with predefined end vertices in metric graphs. This algorithm is due to Hoogeveen and achieves a 5/3-approximation. Here, we characterize hard input instances for Christofides’ algorithm and Hoogeveen’s algorithm by relating the two underlying problems. We show that the sets of metric worst-case instances for both algorithms are disjoint in the following sense: there is an algorithm that, for any input instance, either finds a Hamiltonian tour that is significantly better than 1.5-approximative or a set of Hamiltonian paths between all pairs of endpoints, all of which are significantly better than 5/3-approximative. In the context of approximation algorithms, we also present a new, improved algorithm for the traveling salesman problem, where some vertices have to be visited in a predefined order.

We continue with considering reoptimization problems. There, we handle the question whether the knowledge of an optimal solution to the unaltered instance can help in solving a locally modified instance.

In terms of this idea, we analyze the approximability of the Steiner tree problem. We show that, even in very restricted cases, this problem remains APX -hard. On the one hand, we consider edge costs that are restricted to the values 1 and 1 + γ for an arbitrary small γ 0.

On the other hand, we provide the algorithm with additional information: the input consists of a Steiner tree instance together with an optimal solution, as well as a second Steiner tree instance, where one vertex is added. Now, the goal is to minimize the cost of a solution for the modified input. This way, our result discloses a sharp edge between efficient solvability and inapproximability.

We present the first NP -hardness proofs for the Steiner tree reoptimization problem.

In particular, we show that all Steiner tree reoptimization variants that were previously considered, namely, adding terminals or non-terminals, removing terminals or non-terminals, changing the cost of an edge, and changing the status of a vertex from terminal to nonterminal or vice versa, are NP-hard, even if the edge costs are restricted to the values 1 and 1 + γ for an arbitrary positive γ. For removing terminal or non-terminal vertices, we even show APX -hardness.

The algorithmic results for reoptimization vary considerably, depending on the problem and the type of local modification. The transition from the triangle inequality to the sharpened β-triangle inequality can influence whether there is a PTAS for a problem (assuming vi that P = NP). To this end, we consider the more general class of graphs with a polylogarithmically bounded cost function, where each edge has a cost of at least 1. Then, for some of the Steiner tree reoptimization variants, we even obtain a PTAS. This class of graphs also contains all graphs with a cost function obeying the sharpened β-triangle inequality.

For the Steiner tree problem where the local modification is to change the status of a vertex from terminal to non-terminal or vice versa, we present a 1.5-approximation algorithm, improving the best currently known approximation for the classical minimum Steiner tree problem, which is 1 + (ln 3)/2 ≈ 1.55. We also present results concerning the change of the edge costs as local modification.

Furthermore, we present an analysis of hard instances for the 1.4-approximation algorithm for the traveling salesman reoptimization problem with increasing edge costs from [21] and give several parameters such that any change results in a better approximation ratio. We conclude the reoptimization results by considering the shortest common superstring reoptimization problem. Given a set of strings, the problem consists in finding a shortest superstring that contains each of the given strings as substring. We show that the local modifications of both adding a string and removing a string are NP-hard and we analyze lower bounds on the approximation ratio achievable by a quite natural and promising algorithm for that problem.

The remaining results are concerning complexity theory. All approaches mentioned above depended on the assumption that P = NP holds. For online problems, however, the main focus is on the quality that can be guaranteed at all. Also here, we approach the problem by using novel techniques. We investigate to what extent the solution quality can be improved in terms of advice complexity. We assume that an oracle provides the content of an advice tape. Now the question is, how many of the written bits of advice have to be accessed at most in order to achieve a certain solution quality. We focus on a variant of the job shop √ scheduling problem and show a lower bound of Ω( n) advice bits to be necessary for achieving optimality.

Finally, we handle size complexity of randomized automata. The problem of whether nondeterminism helps is not even answered in computational models as weak as two-way automata. Therefore, we investigate related questions on slightly weaker models. We show that, for any reasonable randomized model, the number of states of sweeping finite automata and rotating finite automata cannot differ more than by a polynomial factor.

vii Acknowledgment I would like to acknowledge the great debt that I owe my advisor, Juraj Hromkoviˇ, who, c with his humble and honest way to deal with people and his extraordinary inspiration and ideas, helped me to develop my abilities as a researcher and, even more important, helped me to grow as a person. He was both a source of invaluable advice on research and of persistent motivation to discover the beauty of the mountains. Due to his infectious verve I discovered some of the most impressive summits of Switzerland.

The camaraderie in our research group was always very pleasant and enjoyable. This was mainly because of all my wonderful colleagues who enabled a constructive and friendly atmosphere. I would like to express my special gratitude to Hans-Joachim B¨ckenhauer, who o never got tired of listening to my ideas, provided constructive criticism of my research, and who made a great effort to proofread this dissertation. Thanks are also due to Christos Kapoutsis, who influenced me to improve my writing skills and to sharpen my perception of details. I also thank Dennis Komm and Richard Kr´loviˇ for the hours of enlightening a c discussions.

In the early days of my graduate studies, I was given the opportunity to visit the King’s College in London. That stay helped me to have a successful start on my research. I would like to thank Kathleen Steinh¨fel wholeheartedly for her invitation and for her hospitality.

o I am also grateful to Ralf Klasing for inviting me to do five weeks of research in the Laboratoire Bordelais de Recherche en Informatique. I will never forget his extraordinary kindness. The fruitful discussions we had in Bordeaux helped me to develop some of the ideas that later on proved to be very important for this dissertation.

I would like to express my heartfelt gratitude to my mother and sister, who always supported me with their love and happiness.

Most of all, I would like to thank my wife Gaya. Meeting her was without doubt the most valuable coincidence of coming to Switzerland.

viii Contents

–  –  –

Introduction This dissertation focuses on new approaches to hard algorithmic problems. There are two main reasons for this: to provide new algorithmic techniques for finding good approximative solutions and to increase the understanding of the essence of the hardness involved.

More specifically, we first investigate approximation and approximability of NP -hard optimization problems. It is to be expected that these problems do not admit any feasible algorithm that guarantees an exact solution within a reasonable time, since it is conjectured that P is not equal to NP. If this conjecture is correct, then there are no exact polynomialtime algorithms for these optimization problems. Thus, instead of trying to find optimal solutions, we aim for good, but not necessarily optimal, solutions.

The research of approximation has led to impressive results. For some NP -hard optimization problems such as the knapsack problem, it is feasible to compute solutions that are very close to optimal ones, using a so called fully polynomial-time approximation scheme [65].

The importance of approximation, however, reaches far beyond its applications in operations research. The NP-hard optimization problems can be classified according to their approximability. This way, we obtain a much more detailed view on the hardness of these problems.

Some deep results in this area were achieved using a characterization of NP via so-called probabilistically checkable proofs [5, 42] which enabled new techniques for showing approximation hardness. Tight bounds on the approximability were shown by H˚ astad [55] for some problems such as MaxE3SAT, the problem to maximize the number of satisfied clauses in a boolean formula, where each clause has exactly three literals.

Despite these achievements, however, there are many important problems for which the known lower bounds on the approximability and the currently best achieved approximation rate differ considerably. One of these problems is the metric traveling salesman problem.

Here, one is given a complete edge-weighted graph with metric cost function and one searches for a minimum-cost cycle that visits each vertex exactly once. A cost function is metric, if no edge between two vertices is more expensive than any path between them. The metric traveling salesman problem is well-known to be approximable within a constant factor of 1.5 due to Christofides’ algorithm [36]. For the best lower bound, however, we only know that finding a better approximation ratio than 117/116 is NP -hard [85].

Due to the long time in which Christofides’ result remains unimproved, it seems worthwhile to have a close look at the properties of hard input instances for his algorithm. In order to do this, we extend the concept of win/win algorithms. The general idea of win/win algorithms is


that we are given two related hard problems defined on the same input instances. Now, we ask whether hard inputs for one problem are also hard for the other one. We tackle this question by searching for algorithms that are guaranteed to find a good solution for at least one of the two problems. This research relates to win/win-strategies in parameterization which provide a popular method for designing parameterized algorithms [44], as well as to the design of hybrid algorithms as used by Vassilevska et al. [108]. In this type of hybrid algorithms, for a single problem, one either finds a good solution efficiently or one is guaranteed to have an improved (exponential) runtime for computing an exact solution.

In contrast to previous approaches, we apply the win/win technique to approximation.

Given two different problems with the same set of input instances, we want to guarantee at least one of the problems to be approximated with a better approximation ratio than the best one we can guarantee by using known algorithms. Besides the algorithmic meaning — we are guaranteed to have a good solution for one of the problems — we classify hard input instances for one algorithm according to the hardness for another algorithm, which is useful for a deeper understanding of why certain input instances are hard.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 16 |

Similar works:

«Chapter 2 Integrated Project DEPLOY Alexander Romanovsky Abstract This chapter introduces the four-year DEPLOY (Industrial Deployment of Advanced System Engineering Methods for High Productivity and Dependability) project to overview the context in which industrial deployment was conducted and explain how it was organised and managed.2.1 DEPLOY Objectives, Consortium and Outcomes The overall aim of the FP7 (EC Seventh Framework Programme) Integrated Project DEPLOY, run between February 2008 and...»

«Nick Feamster Professor feamster@cs.princeton.edu Department of Computer Science http://www.cs.princeton.edu/˜feamster/ Princeton University http://connectionmanagement.org/ 35 Olden Street http://noise-lab.net/ Princeton, NJ 08540 Education Degree Year University Field Ph.D. 2005 Massachusetts Institute of Technology Computer Science Cambridge, MA Dissertation: Proactive Techniques for Correct and Predictable Internet Routing Sprowls Honorable Mention for best MIT Ph.D. dissertation in...»

«J Technol Transf DOI 10.1007/s10961-013-9311-1 Accelerating commercialization: a new model of strategic foundation funding Maryann P. Feldman • Alexandra Graddy-Reed Ó Springer Science+Business Media New York 2013 Abstract Venture philanthropy presents a new model of research funding that is particularly helpful to those fighting orphan diseases, which actively manages the commercialization process to accelerate scientific progress and material outcomes. This paper begins by documenting...»

«Signal-Processing Approaches to Risk Assessment in Coronary Artery Disease I. A. Kakadiaris1, S. M. O’Malley1, M. Vavuranakis2, S. Carlier3, R. Metcalfe4, C. J. Hartley5, E. Falk6, and M. Naghavi7 Department of Computer Science University of Houston Houston, TX, 77204, USA http://www.cs.uh.edu Technical Report Number UH-CS-06-09 June 27, 2006 Keywords: biomedical imaging, intravascular, ultrasound. Abstract Cardiovascular disease has long been the leading cause of death in developed countries...»

«Expressives, Perspective and Presupposition Peter Lasersohn University of Illinois Address: Peter Lasersohn Dept. of Linguistics, MC-168 4080 Foreign Languages Building University of Illinois 707 South Mathews Ave. Urbana, IL 61801 USA E-mail: lasersoh@uiuc.edu Telephone: 1-217-333-1206 List of Symbols: 2@2 (double brackets), á (Greek alpha), â (Greek beta), ó (Greek sigma), g (Greek epsilon), n (Greek phi), C (large dot) Number of Pages: 19 Number of Tables: 0 Number of Figures: 0 Proposed...»

«Depicting Schedule Margin in Integrated Master Schedules National Defense Industrial Association Program Management Systems Committee Schedule Working Group FORWARD The objective of this paper is to discuss practices for depicting Schedule Margin in Integrated Master Schedules and project schedules and to induce collaboration between government and industry for revising related guidance and direction to incorporate these best practices. The desired output of this collaboration is agreement on...»

«South Dakota High School Activities Association D e c e mb e r 4, 2 0 1 4 A u t h o r : B u c k T i mmi n s NFHS RULE AND CASE BOOK CORRECTIONS Rule Book Corrections:  Page 2, 2014-15 NFHS Basketball Rules Changes, 9-1-4g should read 9-1-3g.  Page 55, Rule 9-1-4, Delete.Case Book Corrections:  Pages 25-26, 3.5.4 SITUATION, RULING Correction: illegal equipment in (a); the blue headbands and wristbands do not match the predominant color of the uniform (white).  Page 29, 4.14.1D...»

«Proper Hydration for Distance RunningIdentifying Individual Fluid Needs A USA TRACK & FIELD Advisory Prepared by: Douglas J. Casa, PhD, ATC, FACSM Director, Athletic Training Education University of Connecticut INTRODUCTION Any time a runner hits the road, track, or trail to perform in a race or training session, the need to properly hydrate becomes an issue that will influence the quality of the effort. The evaporation of sweat from the skin’s surface is a powerful cooling mechanism to allow...»

«Sociology of Sport Journal, 2008, 25, 310-330 © 2008 Human Kinetics, Inc. Living on the Edge: The Appeal of Risk Sports for the Professional Middle Class Robert Fletcher Feather River College Early sociological research describes risk sports as a form of resistance to structural aspects of highly industrialized societies. Recent scholarship, however, suggests that conventional social forces operating on the demographic group (young, White, professional, middle-class males) from which most...»

«Bedienungsanleitung Seite 1 von 20 1.1-5x24 Stratos 1.1-5x24 Stratos Schmidt & Bender GmbH & Co. KG • Am Grossacker 42 • D-35444 Biebertal Tel. +49 (0) 64 09-81 15-0 • Fax +49 (0) 64 09-81 15-11 info@schmidt-bender.de • www.schmidt-bender.de Bedienungsanleitung Seite 3 von 20 1.1-5x24 Stratos Beschreibung   1.1  Einleitung 1.2  Sicherheitshinweise Technische Daten   2.1  Allgemeine Daten 2.2  Abmessungen Zubehör / Lieferumfang   Bedienung   4.1  Okulareinstellung 4.2 ...»

«Evaluation of a Broadcast Scheduling Algorithm ¨u Murat Karakaya1 and Ozg¨r Ulusoy2 Department of Technical Sciences Turkish Land Forces Academy, Ankara 06100, Turkey Department of Computer Engineering Bilkent University, Ankara 06533, Turkey muratk@kho.edu.tr, oulusoy@cs.bilkent.edu.tr Abstract. One of the two main approaches of data broadcasting is pullbased data delivery. In this paper, we focus on the problem of scheduling data items to broadcast in such a pull-based environment. Previous...»

«THINK. Before You Choose a Marketing Consultant Copyright © 2013 by Brian Tucker All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means without written permission from the author. Printed in USA. ALL RIGHTS RESERVED. No part of this content may be reproduced or transmitted in any form whatsoever, electronic or mechanical, including photocopying, recording, or by any informational storage or retrieval system without the expressed written, dated...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.