The event takes place:
2012-11-29
PhD: Combinatorial Optimization
PhD: Combinatorial Optimization - Three Applications
Doctoral student Efraim Laksman will defend his doctoral thesis in Mathematics\Discrete Mathematics
on 29 November.
Time: 29 November 2012, at 13:15
Place: Room C216, BTH, Campus Gräsvik, Karlskrona
Thesis title: Combinatorial Optimization - Three Applications
Research education subject: Mathematics\Discrete Mathematics
Supervisor: Docent Håkan Lennerstad, BTH
Chairman of the Faculty Board and examiner: Professor Elisabeth Rakus-Andersson, BTH
Faculty examiner: Docent Johan Wästlund, Chalmers Tekniska Högskola
Examining committee:
- Professor emeritus Ingemar Ingemarsson, Linköping universiity
- Professor Fredrik Manne, University ini Bergen, Norway
- Professor emeritus Per-Olov Lindberg, KTH
Deputy member of examining committee: Docent Niklas Lavesson, BTH
The abstract
Combinatorial optimization is a diverse area of mathematics. It concerns optimization on feasible regions defined by discrete sets, graphs, hypergraphs, matroids, etc. . . which all have a large number of applications. They occur in virtually all domains of human activity since humans always want to do things easier, faster, consume less resources, etc. . . This thesis concerns three applied problems within combinatorial optimization.
The first paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase-shift keying (PSK) block codes, that are explicit in the parameters alphabet size, block length and code size. There is a strong connection between high minimum Euclidean distance and good error-correcting capabilities. The bounds are generalized in several respects, such as from codes on symmetric PSK to codes on asymmetric PSK. They are also generalized to other types of noise than Gaussian, allowing more efficient block codes when noise is non-Gaussian. We provide examples of codes on asymmetric PSK that have higher minimum Euclidean distance than any comparable codes on symmetric PSK.Several classes of codes are shown to be optimal among codes on symmetric PSK since their Euclidean distance coincides with the bound.
The second paper considers a parallel computer system with m identical computers,where we study optimal performance precaution for one possible computer crash. We anticipate that some computer may crash, and restrict the cost in such a situation. How costly is such a precaution when no crash occurs? We set a restriction that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use an optimal allocation with m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time defines a function f(r,m). In the paper we establish upper and lower bounds of the worst-case cost function f(r,m) and characterize worst-case programs.
The third paper considers the problem of Map Matching (MM), i.e. matching time and location measurements of a vehicle to a route in a road network. The paper presents a probabilistic algorithm for MM based on a second order hidden Markov model (HMM), as opposed to first order HMMs which are usually used. This allows a more detailed analysis of the data while preserving algorithmic complexity O(n). Both measurement densities and transition probabilities are determined with respect to Kolmogorov's third axiom, which in this context implies that the probabilities are additive over a partition of a road segment.
Organizer, personal / school / organizer:
School of Engineering
Share