Combinatorial Optimization - Three Applications

Document type: Dissertations
Full text:
Author(s): Efraim Laksman
Title: Combinatorial Optimization - Three Applications
Series: Blekinge Institute of Technology Doctoral Dissertation Series
Year: 2012
Issue: 10
ISSN: 1653-2090
Publisher: Blekinge Institute of Technology
City: Karlskrona
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. Mathematics and Science (Sektionen för teknik – avd. för matematik och naturvetenskap)
School of Engineering S- 371 79 Karlskrona
+46 455 38 50 00
http://www.tek.bth.se/
Authors e-mail: efraim.laksman@bth.se
Language: English
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.
Subject: Mathematics\Discrete Mathematics
URN: urn:nbn:se:bth-00538
Edit