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.
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.
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.
Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Advisors 

Award date  2006 Oct 6 
Publisher  
Print ISBNs  9162869434 
Publication status  Published  2006 
Bibliographical note
Defence detailsDate: 20061006
Time: 13:15
Place: Room E:1406, Ebuilding, Lund Institute of Technology, Ole Römers väg 3, Lund, Sweden
External reviewer(s)
Name: Gasieniec, Leszek
Title: Professor
Affiliation: Department of Computer Science,The University of Liverpool,Ashton Building, Ashton StreetLiver

<div class="article_info">Andres Figueroa, Avraham Goldstein, Tao Jiang, Maciej Kurowski, Andrzej Lingas and Mia Persson. <span class="article_issue_date">2005</span>. <span class="article_title">Approximate Clustering of Fingerprint Vectors with Missing Values.</span> <span class="journal_pages">pp 5760</span>. <span class="journal_distributor">Australian Computer Society, Inc.</span></div>
<div class="article_info">Anders Dessmark, Jesper Jansson, Andrzej Lingas, EvaMarta Lundell and Mia Persson. <span class="article_issue_date">2006</span>. <span class="article_title">On the Approximability of Maximum and Minimum Edge Clique Partition Problems</span> <span class="journal_series_title">International Journal of Foundations of Computer Science</span>, <span class="journal_distributor">World Scientific</span> (accepted)</div>
<div class="article_info">Mikael Hammar, Bengt J. Nilsson and Mia Persson. <span class="article_issue_date">2006</span>. <span class="article_title">Competitive Exploration of Rectilinear Polygons</span> <span class="journal_series_title">Theoretical Computer Science (Foundations of computation theory (FCT 2003) special issue)</span>, <span class="journal_volume">vol 354</span> <span class="journal_pages">pp 367378</span>. <span class="journal_distributor">Elsevier Science Publishers Ltd</span></div>
<div class="article_info">Mikael Hammar, Bengt J. Nilsson and Mia Persson. <span class="article_issue_date">2006</span>. <span class="article_title">The Online Freezetag Problem</span> <span class="journal_pages">pp 569579</span>. <span class="journal_distributor">Springer</span></div>
<div class="article_info">Andrzej Lingas, Mia Persson and Martin Wahlen. <span class="article_issue_date">2006</span>. <span class="article_title">MinimumEnergy Broadcasting in Wireless Networks in the ddimensional Euclidean Space (the $alpha le d$ case)</span> <span class="journal_pages">pp 112124</span>. <span class="journal_distributor">Springer</span> (inpress)</div>
Subject classification (UKÄ)
 Computer Science
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