Optimization, Matroids and Error-Correcting Codes

Sammanfattning: The first subject we investigate in this thesis deals with optimization problems on graphs. The edges are given costs defined by the values of independent exponential random variables. We show how to calculate some or all moments of the distributions of the costs of some optimization problems on graphs.The second subject that we investigate is 1-error correcting perfect binary codes, perfect codes for short. In most work about perfect codes, two codes are considered equivalent if there is an isometric mapping between them. We call this isometric equivalence. Another type of equivalence is given if two codes can be mapped on each other using a non-singular linear map. We call this linear equivalence. A third type of equivalence is given if two codes can be mapped on each other using a composition of an isometric map and a non-singular linear map. We call this extended equivalence.In Paper 1 we give a new better bound on how much the cost of the matching problem with exponential edge costs varies from its mean.In Paper 2 we calculate the expected cost of an LP-relaxed version of the matching problem where some edges are given zero cost. A special case is when the vertices with probability 1 – p have a zero cost loop, for this problem we prove that the expected cost is given by a formula.In Paper 3 we define the polymatroid assignment problem and give a formula for calculating all moments of its cost.In Paper 4 we present a computer enumeration of the 197 isometric equivalence classes of the perfect codes of length 31 of rank 27 and with a kernel of dimension 24.In Paper 5 we investigate when it is possible to map two perfect codes on each other using a non-singular linear map.In Paper 6 we give an invariant for the equivalence classes of all perfect codes of all lengths when linear equivalence is considered.In Paper 7 we give an invariant for the equivalence classes of all perfect codes of all lengths when extended equivalence is considered.In Paper 8 we define a class of perfect codes that we call FRH-codes. It is shown that each FRH-code is linearly equivalent to a so called Phelps code and that this class contains Phelps codes as a proper subset.