Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry

Persson, Mia LU (2006)
Abstract
The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. The thesis is divided into two parts. In the first part we study some problems where one seeks to find a (possibly hierarchical) clustering of a set of objects such that particular objective functions are either maximized or minimized. We study the computational complexity, present polynomial-time... (More)
The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. The thesis is divided into two parts. In the first part we study some problems where one seeks to find a (possibly hierarchical) clustering of a set of objects such that particular objective functions are either maximized or minimized. We study the computational complexity, present polynomial-time approximation algorithms or derive bounds on the allowed degree of approximability achievable in polynomial time for these problems.



The second part is devoted to decision making based on only partial information on the input. We present online algorithms for two problems with applications in the area of robotics and use the well established approach of competitive analysis to analyze their performance. We also study lower bounds, aiming at establishing to what extent the problems can be approximated. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Gasieniec, Leszek, Department of Computer Science,The University of Liverpool,Ashton Building, Ashton StreetLiver
organization
publishing date
type
Thesis
publication status
published
subject
keywords
numerisk analys, system, systems, control, Datalogi, numerical analysis, broadcasting, polygon exploration, robotics, Mathematics, Matematik, Computer science, clique partition, clustering, computational complexity, computational geometry, computational biology, online algorithm, kontroll, approximation algorithm
pages
105 pages
publisher
Department of Computer Science, Lund University
defense location
Room E:1406, E-building, Lund Institute of Technology, Ole Römers väg 3, Lund, Sweden
defense date
2006-10-06 13:15:00
ISBN
91-628-6943-4
language
English
LU publication?
yes
additional info
id
6b388e7c-8a31-49fc-ac24-0ed0119b49ae (old id 547213)
date added to LUP
2016-04-01 16:28:57
date last changed
2018-11-21 20:41:44
@phdthesis{6b388e7c-8a31-49fc-ac24-0ed0119b49ae,
  abstract     = {The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. The thesis is divided into two parts. In the first part we study some problems where one seeks to find a (possibly hierarchical) clustering of a set of objects such that particular objective functions are either maximized or minimized. We study the computational complexity, present polynomial-time approximation algorithms or derive bounds on the allowed degree of approximability achievable in polynomial time for these problems.<br/><br>
<br/><br>
The second part is devoted to decision making based on only partial information on the input. We present online algorithms for two problems with applications in the area of robotics and use the well established approach of competitive analysis to analyze their performance. We also study lower bounds, aiming at establishing to what extent the problems can be approximated.},
  author       = {Persson, Mia},
  isbn         = {91-628-6943-4},
  language     = {eng},
  publisher    = {Department of Computer Science, Lund University},
  school       = {Lund University},
  title        = {Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry},
  year         = {2006},
}