A New Class of Heuristic Algorithms for Weighted Perfect Matching

M. D. Grigoriadis, Bahman Kalantari

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k ≤ log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of ƒ(n) times the optimal weight, an O(max{n2, t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.

Original languageEnglish (US)
Pages (from-to)769-776
Number of pages8
JournalJournal of the ACM (JACM)
Volume35
Issue number4
DOIs
StatePublished - Oct 1 1988

Fingerprint

Heuristic algorithms

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Approximate algorithms
  • Euler tours
  • Hamiltonians
  • combinatorial optimization
  • complexity
  • heuristics
  • matching

Cite this

@article{c3d7b8199e8f4463b6cc4703a0c0989d,
title = "A New Class of Heuristic Algorithms for Weighted Perfect Matching",
abstract = "The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k ≤ log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of ƒ(n) times the optimal weight, an O(max{n2, t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.",
keywords = "Approximate algorithms, Euler tours, Hamiltonians, combinatorial optimization, complexity, heuristics, matching",
author = "Grigoriadis, {M. D.} and Bahman Kalantari",
year = "1988",
month = "10",
day = "1",
doi = "10.1145/48014.48015",
language = "English (US)",
volume = "35",
pages = "769--776",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

A New Class of Heuristic Algorithms for Weighted Perfect Matching. / Grigoriadis, M. D.; Kalantari, Bahman.

In: Journal of the ACM (JACM), Vol. 35, No. 4, 01.10.1988, p. 769-776.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A New Class of Heuristic Algorithms for Weighted Perfect Matching

AU - Grigoriadis, M. D.

AU - Kalantari, Bahman

PY - 1988/10/1

Y1 - 1988/10/1

N2 - The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k ≤ log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of ƒ(n) times the optimal weight, an O(max{n2, t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.

AB - The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k ≤ log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of ƒ(n) times the optimal weight, an O(max{n2, t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.

KW - Approximate algorithms

KW - Euler tours

KW - Hamiltonians

KW - combinatorial optimization

KW - complexity

KW - heuristics

KW - matching

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

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

U2 - 10.1145/48014.48015

DO - 10.1145/48014.48015

M3 - Article

VL - 35

SP - 769

EP - 776

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 4

ER -