On the Hamming distance in combinatorial optimization problems on hypergraph matchings

Alla Kammerdiner; Pavlo A. Krokhmal; Panos M. Pardalos

doi:10.1007/s11590-010-0187-9

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

Alla Kammerdiner, Pavlo A. Krokhmal, Panos M. Pardalos

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.

Original language	English (US)
Pages (from-to)	609-617
Number of pages	9
Journal	Optimization Letters
Volume	4
Issue number	4
DOIs	https://doi.org/10.1007/s11590-010-0187-9
State	Published - 2010
Externally published	Yes

Keywords

Combinatorial optimization
Hamming distance
Hypergraph matchings
Multidimensional assignment problem

ASJC Scopus subject areas

Business, Management and Accounting (miscellaneous)
Control and Optimization

Access to Document

10.1007/s11590-010-0187-9

Cite this

@article{6cf2d43156c94a609575411f54d58fe0,

title = "On the Hamming distance in combinatorial optimization problems on hypergraph matchings",

abstract = "In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.",

keywords = "Combinatorial optimization, Hamming distance, Hypergraph matchings, Multidimensional assignment problem",

author = "Alla Kammerdiner and Krokhmal, {Pavlo A.} and Pardalos, {Panos M.}",

note = "Funding Information: Supported in part by AFOSR grant FA9550-09-1-0088.",

year = "2010",

doi = "10.1007/s11590-010-0187-9",

language = "English (US)",

volume = "4",

pages = "609--617",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "4",

}

TY - JOUR

T1 - On the Hamming distance in combinatorial optimization problems on hypergraph matchings

AU - Kammerdiner, Alla

AU - Krokhmal, Pavlo A.

AU - Pardalos, Panos M.

N1 - Funding Information: Supported in part by AFOSR grant FA9550-09-1-0088.

PY - 2010

Y1 - 2010

N2 - In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.

AB - In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.

KW - Combinatorial optimization

KW - Hamming distance

KW - Hypergraph matchings

KW - Multidimensional assignment problem

UR - http://www.scopus.com/inward/record.url?scp=77956885869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956885869&partnerID=8YFLogxK

U2 - 10.1007/s11590-010-0187-9

DO - 10.1007/s11590-010-0187-9

M3 - Article

AN - SCOPUS:77956885869

SN - 1862-4472

VL - 4

SP - 609

EP - 617

JO - Optimization Letters

JF - Optimization Letters

IS - 4

ER -

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this