Evenemanget pågår:
2012-11-29
PhD: Combinatorial Optimization - Three Applica...
PhD: Combinatorial Optimization - Three Applications
Doktorand Efraim Laksman försvarar sin doktorsavhandling i ämnet Matematik med tillämpningar den 29 november.
Tid: 29 november 2012 kl. 13:15
Plats: Sal C216, BTH, Campus Gräsvik, Karlskrona
Avhandlingens titel: Combinatorial Optimization - Three Applications
Forskarutbildningsämne: Matematik med tillämpningar
Handledare: Docent Håkan Lennerstad, BTH
Ordförande och examinator: Professor Elisabeth Rakus-Andersson, BTH
Opponent: Docent Johan Wästlund, Chalmers Tekniska Högskola
Betygsnämnd:
- Professor emeritus Ingemar Ingemarsson, Linköpings universitet
- Professor Fredrik Manne, Universitetet i Bergen, Norge
- Professor emeritus Per-Olov Lindberg, Kungliga Tekniska Högskolan
Betygsnämndssuppleant:
Docent Niklas Lavesson, BTH
Anmälan om deltagande görs till forskningsadministration BTH-ING senast den 16 november.
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.
Arrangör, person/sektion/organisatör:
Sektionen för ingenjörsvetenskap
Dela