liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimization, Matroids and Error-Correcting Codes
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2009. , 55 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1277
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-51722ISBN: 978-91-7393-521-0 (print)OAI: oai:DiVA.org:liu-51722DiVA: diva2:277130
Public defence
2009-12-16, Nobel (BL32), hus B, ing. 23, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2010-01-12Bibliographically approved
List of papers
1. Concentration of the cost of a random matching problem
Open this publication in new window or tab >>Concentration of the cost of a random matching problem
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Let Mn be the minimum cost of a perfect matching on a complete graph on n vertices whose edges are assigned independent exponential costs. It follows from work of D. Aldous that Mn converges in probability to π2/12. This was earlier conjectured by M. Mézard and G. Parisi. We establish the more precise result that E | Mn – π2/12| = O(n-1/2).

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51715 (URN)
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2009-11-16Bibliographically approved
2. LP-relaxed matching with zero-cost loops
Open this publication in new window or tab >>LP-relaxed matching with zero-cost loops
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We study a certain LP-relaxation of the minimum matching problem on a complete graph with random edge costs. In earlier work by Wästlund it was shown that the expected cost of the optimum solution has the simple form 1 – 1/4 + 1/9 – ··· ± 1/n2, an analogue of a corresponding formula for the bipartite problem. Wegeneralize by conditioning on certain edges having zero cost. It is proved that if each node independently is given a zero-cost loop with probability 1 ¡ p then the expected cost of the optimum solution is p – p2/4 + p3/9 – ··· ± pn/n2.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51716 (URN)
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2009-11-16Bibliographically approved
3. The polymatroid assignment problem
Open this publication in new window or tab >>The polymatroid assignment problem
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In 1998 G. Parisi published the two page note, with the conjecturedexact formula for the random bipartite matching (or assignment) problemwith exponential edge costs. This formula was subsequently proved and generalized in different directions. One such generalization given in was called the flow problem. Here we take the generalization process one step further. In a two-dimensional urn-processwas developed in order to calculate all moments of the cost of the flow problem. This process is here generalized to a larger class of optimization problems on the bipartite graph. These problems are defined by assigning a polymatroid structure to each of the two sets of vertices. An edge set isa feasible solution to the optimization problem if the two associated vertex(multi-)sets are both independent. Our main theorem states that the moments of the cost of the polymatroid assignment problem are characterizedby the associated urn process. We apply this theorem to some concrete problems which are not covered by previously known generalization of the bipartite matching problem.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51717 (URN)
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2009-11-16Bibliographically approved
4. A computer study of some 1-error correcting perfect binary codes
Open this publication in new window or tab >>A computer study of some 1-error correcting perfect binary codes
2005 (English)In: Australasian journal of combinatorics, ISSN 1034-4942, Vol. 33, 217-229 p.Article in journal (Refereed) Published
Abstract [en]

A general algrothm for classifying 1-error correction perfect binary codes of length n, rank n – log2(n+1)+1 and kernel of dimension n – log2/n+1) – 2 is presented. The algorithm gives for n = 31.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-31627 (URN)17433 (Local ID)17433 (Archive number)17433 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2009-11-16Bibliographically approved
5. Perfect codes as isomorphic spaces
Open this publication in new window or tab >>Perfect codes as isomorphic spaces
2006 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 306, no 16, 1981-1987 p.Article in journal (Refereed) Published
Abstract [en]

Linear equivalence between perfect codes is defined. This definition gives the concept of general perfect 1-error correcting binary codes. These are defined as 1-error correcting perfect binary codes, with the difference that the set of errors is not the set of weight one words, instead any set with cardinality n and full rank is allowed. The side class structure defines the restrictions on the subspace of any general 1-error correcting perfect binary code. Every linear equivalence class will contain all codes with the same length, rank and dimension of kernel and all codes in the linear equivalence class will have isomorphic side class structures.

Place, publisher, year, edition, pages
Elsevier, 2006
Keyword
Perfect codes; Dual codes; Classification
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51718 (URN)10.1016/j.disc.2006.03.039 (DOI)000240173300018 ()
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2012-08-17Bibliographically approved
6. On the classification of perfect codes: Side class structures
Open this publication in new window or tab >>On the classification of perfect codes: Side class structures
2006 (English)In: Designs, Codes and Cryptography, ISSN 0925-1022, Vol. 40, no 3, 319-333 p.Article in journal (Refereed) Published
Abstract [en]

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C' are linearly equivalent if there exists a non-singular matrix A such that AC = C' where C and C' are matrices with the code words of C and C' as columns. Hessler proved that the perfect codes C and C' are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa, any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes. © Springer Science + Business Media, LLC 2006.

Keyword
Perfect codes, Tilings
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-50133 (URN)10.1007/s10623-006-0024-4 (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2009-11-16Bibliographically approved
7. On the classification of perfect codes: Extended side class structures
Open this publication in new window or tab >>On the classification of perfect codes: Extended side class structures
2010 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 310, no 1, 43-55 p.Article in journal (Refereed) Published
Abstract [en]

The two 1-error correcting perfect binary codes, C and C are said to be equivalent if there exists a permutation π of the set of the n coordinate positions and a word such that . Hessler defined C and C to be linearly equivalent if there exists a non-singular linear map φ such that C=φ(C). Two perfect codes C and C of length n will be defined to be extended equivalent if there exists a non-singular linear map φ and a word such that

Heden and Hessler, associated with each linear equivalence class an invariant LC and this invariant was shown to be a subspace of the kernel of some perfect code. It is shown here that, in the case of extended equivalence, the corresponding invariant will be the extension of the code LC.

This fact will be used to give, in some particular cases, a complete enumeration of all extended equivalence classes of perfect codes.

Place, publisher, year, edition, pages
Amsterdam, Netherlands: Elsevier, 2010
Keyword
Perfect codes, Side class structures
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51719 (URN)10.1016/j.disc.2009.07.023 (DOI)000272437800007 ()
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2014-01-13Bibliographically approved
8. On linear equivalence and Phelps codes
Open this publication in new window or tab >>On linear equivalence and Phelps codes
(English)Manuscript (preprint) (Other academic)
Abstract [en]

It is shown that all the non full rank FRH-codes, a class of perfect codes we define in the paper, are linearly equivalent to perfect codes obtainable by Phelps construction. It is shown by an example that this class of perfect codes also contains perfect codes that are not obtainable by Phelps construction.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-51720 (URN)
Available from: 2009-11-16 Created: 2009-11-16 Last updated: 2009-11-16Bibliographically approved

Open Access in DiVA

Optimization, Matroids and Error-Correcting Codes(685 kB)1738 downloads
File information
File name FULLTEXT02.pdfFile size 685 kBChecksum SHA-512
d6212f69466e8dd10b9475f4e13f14dc38a5b9fbeaf11131b078d9a7bc8859c7952116065822e446d2c80d5de1df9842d6421b2c8b6cf1da2ed60d8c2e9138bb
Type fulltextMimetype application/pdf
Cover(56 kB)37 downloads
File information
File name COVER01.pdfFile size 56 kBChecksum SHA-512
2b84d59afc2cefe2c7077319f50c7353cec11606298f4d5a582b432883d4d3dfd652cbb82f6a1fa56c0fee28835feb9bdb4adebcfbd5beb40a0f99a6e197ece7
Type coverMimetype application/pdf

Authority records BETA

Hessler, Martin

Search in DiVA

By author/editor
Hessler, Martin
By organisation
Applied MathematicsThe Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1738 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1873 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf