ISBN 9783843949996

978-3-8439-4999-6, Reihe Mathematik

Tobias Bernd Dietz
Combinatorial Optimization in Digital Communications

163 Seiten, Dissertation Technische Universität Kaiserslautern (2022), Hardcover, A5

Zusammenfassung / Abstract

This thesis is divided into three parts. In the first part, we cover three kinds of problems: Optimal paths with respect to the path length, the binary knapsack problem, and optimal paths with respect to the path quality. For each problem, we define terms of optimality, develop algorithms to solve the problems and analyze running times and memory requirements.

The second part of this thesis covers multicriteria optimization, a topic related to optimal paths with respect to path quality. Instead of a single multicriteria problem, we consider a set of these problems that are interconnected by side constraints, a so-called complex system. Every single problem represents one party of a mutual project, where each party has its individual objectives and constraints. We develop a graph-based model to describe interactions and relations between the single systems. Then we define a new, more general term of efficiency, and compare this with the common concept of efficiency for one single system.

In the second chapter of this part, we develop a new algorithm to decompose the weight space of a multicriteria problem with three objective functions.

In the third part, we optimize matrices that represent a linear binary code, which is a problem emerging from decoding theory. Given a binary matrix, wesearch for a matrix with the same dimension and kernel such that the number of one-entries is minimized. We show that this problem is NP-hard and formulate an integer program in order to solve the problem. Due to running time constraints, we further compute lower bounds via another integer program and give heuristics forfurther optimization.

Last, we develop a new, faster algorithm to project a vector onto the parity polytope, which is a crucial step in the alternating direction method of multipliers decoding method.