Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry
(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 polynomialtime... (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 polynomialtime 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:
https://lup.lub.lu.se/record/547213
 author
 Persson, Mia ^{LU}
 supervisor

 Andrzej Lingas ^{LU}
 Bengt Nilsson
 opponent

 Professor Gasieniec, Leszek, Department of Computer Science,The University of Liverpool,Ashton Building, Ashton StreetLiver
 organization
 publishing date
 2006
 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, Ebuilding, Lund Institute of Technology, Ole Römers väg 3, Lund, Sweden
 defense date
 20061006 13:15:00
 ISBN
 9162869434
 language
 English
 LU publication?
 yes
 additional info
 Andres Figueroa, Avraham Goldstein, Tao Jiang, Maciej Kurowski, Andrzej Lingas and Mia Persson. 2005. Approximate Clustering of Fingerprint Vectors with Missing Values. pp 5760. Australian Computer Society, Inc.Anders Dessmark, Jesper Jansson, Andrzej Lingas, EvaMarta Lundell and Mia Persson. 2006. On the Approximability of Maximum and Minimum Edge Clique Partition Problems International Journal of Foundations of Computer Science, World Scientific (accepted)Mikael Hammar, Bengt J. Nilsson and Mia Persson. 2006. Competitive Exploration of Rectilinear Polygons Theoretical Computer Science (Foundations of computation theory (FCT 2003) special issue), vol 354 pp 367378. Elsevier Science Publishers LtdMikael Hammar, Bengt J. Nilsson and Mia Persson. 2006. The Online Freezetag Problem pp 569579. SpringerAndrzej Lingas, Mia Persson and Martin Wahlen. 2006. MinimumEnergy Broadcasting in Wireless Networks in the ddimensional Euclidean Space (the $alpha le d$ case) pp 112124. Springer (inpress)
 id
 6b388e7c8a3149fcac240ed0119b49ae (old id 547213)
 date added to LUP
 20160401 16:28:57
 date last changed
 20181121 20:41:44
@phdthesis{6b388e7c8a3149fcac240ed0119b49ae, 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 polynomialtime 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 = {{9162869434}}, 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}}, 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}}, }