A generic algorithm for approximately solving stochastic graph optimization problems

Ei Ando; Hirotaka Ono; Masafumi Yamashita

doi:10.1007/978-3-642-04944-6_8

A generic algorithm for approximately solving stochastic graph optimization problems

Ei Ando, Hirotaka Ono, Masafumi Yamashita

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a (directed or undirected) graph G = (V,E), a mutually independent random variable X_e obeying a normal distribution for each edge e ∈ E that represents its edge weight, and a property P on graph, a stochastic graph maximization problem asks the distribution function F _MAX(x) of random variable X_MAX = max_P∈P Σ_e∈A X_e, where property P is identified with the set of subgraphs P = (U,A) of G having P. This paper proposes a generic algorithm for computing an elementary function F̃(x) that approximates F_MAX(x). It is applicable to any P and runs in time O(T _AMAX(P)+T_ACNT(P)), provided the existence of an algorithm A_MAX that solves the (deterministic) graph maximization problem for P in time T_AMAX(P) and an algorithm A_CNT that outputs an upper bound on |P| in time T_ACNT(P).We analyze the approximation ratio and apply it to three graph maximization problems. In case no efficient algorithms are known for solving the graph maximization problem for P, an approximation algorithm A_APR can be used instead of A_MAX to reduce the time complexity, at the expense of increase of approximation ratio. Our algorithm can be modified to handle minimization problems.

Original language	English
Title of host publication	Stochastic Algorithms
Subtitle of host publication	Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings
Pages	89-103
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-04944-6_8
Publication status	Published - 2009
Event	5th Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009 - Sapporo, Japan Duration: Oct 26 2009 → Oct 28 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5792 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	5th Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009
Country/Territory	Japan
City	Sapporo
Period	10/26/09 → 10/28/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-04944-6_8

Cite this

Ando, E., Ono, H., & Yamashita, M. (2009). A generic algorithm for approximately solving stochastic graph optimization problems. In Stochastic Algorithms: Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings (pp. 89-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5792 LNCS). https://doi.org/10.1007/978-3-642-04944-6_8

A generic algorithm for approximately solving stochastic graph optimization problems. / Ando, Ei; Ono, Hirotaka; Yamashita, Masafumi.
Stochastic Algorithms: Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings. 2009. p. 89-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5792 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ando, E, Ono, H & Yamashita, M 2009, A generic algorithm for approximately solving stochastic graph optimization problems. in Stochastic Algorithms: Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5792 LNCS, pp. 89-103, 5th Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009, Sapporo, Japan, 10/26/09. https://doi.org/10.1007/978-3-642-04944-6_8

Ando E, Ono H, Yamashita M. A generic algorithm for approximately solving stochastic graph optimization problems. In Stochastic Algorithms: Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings. 2009. p. 89-103. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04944-6_8

Ando, Ei ; Ono, Hirotaka ; Yamashita, Masafumi. / A generic algorithm for approximately solving stochastic graph optimization problems. Stochastic Algorithms: Foundations and Applications - 5th International Symposium, SAGA 2009, Proceedings. 2009. pp. 89-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{95ef9162e5274cada185482359fd4437,

title = "A generic algorithm for approximately solving stochastic graph optimization problems",

abstract = "Given a (directed or undirected) graph G = (V,E), a mutually independent random variable Xe obeying a normal distribution for each edge e ∈ E that represents its edge weight, and a property P on graph, a stochastic graph maximization problem asks the distribution function F MAX(x) of random variable XMAX = maxP∈P Σe∈A Xe, where property P is identified with the set of subgraphs P = (U,A) of G having P. This paper proposes a generic algorithm for computing an elementary function {\~F}(x) that approximates FMAX(x). It is applicable to any P and runs in time O(T AMAX(P)+TACNT(P)), provided the existence of an algorithm AMAX that solves the (deterministic) graph maximization problem for P in time TAMAX(P) and an algorithm ACNT that outputs an upper bound on |P| in time TACNT(P).We analyze the approximation ratio and apply it to three graph maximization problems. In case no efficient algorithms are known for solving the graph maximization problem for P, an approximation algorithm AAPR can be used instead of AMAX to reduce the time complexity, at the expense of increase of approximation ratio. Our algorithm can be modified to handle minimization problems.",

author = "Ei Ando and Hirotaka Ono and Masafumi Yamashita",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 5th Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009 ; Conference date: 26-10-2009 Through 28-10-2009",

year = "2009",

doi = "10.1007/978-3-642-04944-6_8",

language = "English",

isbn = "3642049435",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "89--103",

booktitle = "Stochastic Algorithms",

}

TY - GEN

T1 - A generic algorithm for approximately solving stochastic graph optimization problems

AU - Ando, Ei

AU - Ono, Hirotaka

AU - Yamashita, Masafumi

PY - 2009

Y1 - 2009

N2 - Given a (directed or undirected) graph G = (V,E), a mutually independent random variable Xe obeying a normal distribution for each edge e ∈ E that represents its edge weight, and a property P on graph, a stochastic graph maximization problem asks the distribution function F MAX(x) of random variable XMAX = maxP∈P Σe∈A Xe, where property P is identified with the set of subgraphs P = (U,A) of G having P. This paper proposes a generic algorithm for computing an elementary function F̃(x) that approximates FMAX(x). It is applicable to any P and runs in time O(T AMAX(P)+TACNT(P)), provided the existence of an algorithm AMAX that solves the (deterministic) graph maximization problem for P in time TAMAX(P) and an algorithm ACNT that outputs an upper bound on |P| in time TACNT(P).We analyze the approximation ratio and apply it to three graph maximization problems. In case no efficient algorithms are known for solving the graph maximization problem for P, an approximation algorithm AAPR can be used instead of AMAX to reduce the time complexity, at the expense of increase of approximation ratio. Our algorithm can be modified to handle minimization problems.

AB - Given a (directed or undirected) graph G = (V,E), a mutually independent random variable Xe obeying a normal distribution for each edge e ∈ E that represents its edge weight, and a property P on graph, a stochastic graph maximization problem asks the distribution function F MAX(x) of random variable XMAX = maxP∈P Σe∈A Xe, where property P is identified with the set of subgraphs P = (U,A) of G having P. This paper proposes a generic algorithm for computing an elementary function F̃(x) that approximates FMAX(x). It is applicable to any P and runs in time O(T AMAX(P)+TACNT(P)), provided the existence of an algorithm AMAX that solves the (deterministic) graph maximization problem for P in time TAMAX(P) and an algorithm ACNT that outputs an upper bound on |P| in time TACNT(P).We analyze the approximation ratio and apply it to three graph maximization problems. In case no efficient algorithms are known for solving the graph maximization problem for P, an approximation algorithm AAPR can be used instead of AMAX to reduce the time complexity, at the expense of increase of approximation ratio. Our algorithm can be modified to handle minimization problems.

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

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

U2 - 10.1007/978-3-642-04944-6_8

DO - 10.1007/978-3-642-04944-6_8

M3 - Conference contribution

AN - SCOPUS:78650651188

SN - 3642049435

SN - 9783642049439

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 89

EP - 103

BT - Stochastic Algorithms

T2 - 5th Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009

Y2 - 26 October 2009 through 28 October 2009

ER -

A generic algorithm for approximately solving stochastic graph optimization problems

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this