Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

Abraham P. Punnen; Ruonan Zhang

doi:10.1016/j.disopt.2012.05.002

Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

Abraham P. Punnen^*, Ruonan Zhang

^*Corresponding author for this work

Simon Fraser University

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

4 Citations (Scopus)

Abstract

In this note, we show that if the maximum clique problem can be solved by a polynomial time δ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(pδ-1)p-1-approximation algorithm for any fixed integer p<2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic.

Original language	English
Pages (from-to)	205-208
Number of pages	4
Journal	Discrete Optimization
Volume	9
Issue number	3
DOIs	https://doi.org/10.1016/j.disopt.2012.05.002
Publication status	Published - Aug 2012
Externally published	Yes

Keywords

Approximation algorithm
Clique partition
Maximum clique

Access to Document

10.1016/j.disopt.2012.05.002

Cite this

@article{d6822e7cb5f94685b914151b6d69f175,

title = "Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem",

abstract = "In this note, we show that if the maximum clique problem can be solved by a polynomial time δ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(pδ-1)p-1-approximation algorithm for any fixed integer p<2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic.",

keywords = "Approximation algorithm, Clique partition, Maximum clique",

author = "Punnen, {Abraham P.} and Ruonan Zhang",

note = "Funding Information: This work was supported by an NSERC discovery grant awarded to Abraham P. Punnen.",

year = "2012",

month = aug,

doi = "10.1016/j.disopt.2012.05.002",

language = "English",

volume = "9",

pages = "205--208",

journal = "Discrete Optimization",

issn = "1572-5286",

number = "3",

}

TY - JOUR

T1 - Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

AU - Punnen, Abraham P.

AU - Zhang, Ruonan

N1 - Funding Information: This work was supported by an NSERC discovery grant awarded to Abraham P. Punnen.

PY - 2012/8

Y1 - 2012/8

N2 - In this note, we show that if the maximum clique problem can be solved by a polynomial time δ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(pδ-1)p-1-approximation algorithm for any fixed integer p<2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic.

AB - In this note, we show that if the maximum clique problem can be solved by a polynomial time δ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(pδ-1)p-1-approximation algorithm for any fixed integer p<2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic.

KW - Approximation algorithm

KW - Clique partition

KW - Maximum clique

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

U2 - 10.1016/j.disopt.2012.05.002

DO - 10.1016/j.disopt.2012.05.002

M3 - Article

AN - SCOPUS:84865144913

SN - 1572-5286

VL - 9

SP - 205

EP - 208

JO - Discrete Optimization

JF - Discrete Optimization

IS - 3

ER -

Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this