Optimizing misdirection

Piotr Berman; Piotr Krysta

Optimizing misdirection

Piotr Berman, Piotr Krysta

Research output: Contribution to conference › Paper › peer-review

Abstract

In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w: V → R₊, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a "misdirected" criterion, i.e. w^α(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.

Original language	English (US)
Pages	192-201
Number of pages	10
State	Published - Jan 1 2003
Event	Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998

Other

Other	Configuralble Computing: Technology and Applications
Country/Territory	United States
City	Boston, MA
Period	11/2/98 → 11/3/98

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@conference{8aef58361e2c4dac87b9aabc38c1de3e,

title = "Optimizing misdirection",

abstract = "In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w: V → R+, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a {"}misdirected{"} criterion, i.e. wα(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.",

author = "Piotr Berman and Piotr Krysta",

year = "2003",

month = jan,

day = "1",

language = "English (US)",

pages = "192--201",

note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

TY - CONF

T1 - Optimizing misdirection

AU - Berman, Piotr

AU - Krysta, Piotr

PY - 2003/1/1

Y1 - 2003/1/1

N2 - In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w: V → R+, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a "misdirected" criterion, i.e. wα(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.

AB - In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w: V → R+, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a "misdirected" criterion, i.e. wα(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.

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

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

M3 - Paper

AN - SCOPUS:0038416101

SP - 192

EP - 201

T2 - Configuralble Computing: Technology and Applications

Y2 - 2 November 1998 through 3 November 1998

ER -

Optimizing misdirection

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this