Change search
ReferencesLink to record
Permanent link

Direct link
Combinatorial Optimization: Three Applications
Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Karlskrona: Blekinge Institute of Technology , 2012.
Blekinge Institute of Technology Doctoral Dissertation Series, ISSN 1653-2090 ; 10
National Category
Mathematical Analysis
URN: urn:nbn:se:bth-00538Local ID: diva2:834817
Available from: 2012-10-31 Created: 2012-10-02 Last updated: 2016-09-06Bibliographically approved

Open Access in DiVA

fulltext(1249 kB)41 downloads
File information
File name FULLTEXT01.pdfFile size 1249 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Laksman, Efraim
By organisation
Department of Mathematics and Natural Sciences
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar
Total: 41 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 38 hits
ReferencesLink to record
Permanent link

Direct link