An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity

Edward Gimadi

doi:10.1007/978-3-319-73013-4_27

An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

Аннотация

The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm³) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm^2.5) time.

Язык оригинала	английский
Название основной публикации	Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
Редакторы	WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
Издатель	Springer-Verlag GmbH and Co. KG
Страницы	295-303
Число страниц	9
ISBN (печатное издание)	9783319730127
DOI	https://doi.org/10.1007/978-3-319-73013-4_27
Состояние	Опубликовано - 1 янв 2018
Событие	6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Российская Федерация Продолжительность: 27 июл 2017 → 29 июл 2017

Серия публикаций

Название	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том	10716 LNCS
ISSN (печатное издание)	0302-9743
ISSN (электронное издание)	1611-3349

Конференция

Конференция	6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Страна	Российская Федерация
Город	Moscow
Период	27.07.2017 → 29.07.2017

Доступ к документу

10.1007/978-3-319-73013-4_27

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Gimadi, E. (2018). An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. В WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Ред.), Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (стр. 295-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-73013-4_27

Gimadi, Edward. / An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. редактор / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. стр. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8fe382acd4b94815806c82fc5119e278,

title = "An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity",

abstract = "The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm3) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm2.5) time.",

keywords = "Dynamic programming, Exact algoritm, Outerplanar graph, Time complexity, Time complexity Dynamic programming, TREES",

author = "Edward Gimadi",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-73013-4_27",

language = "English",

isbn = "9783319730127",

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

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "295--303",

editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",

booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",

address = "Germany",

note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",

}

Gimadi, E 2018, An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. в WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko & S Wasserman (ред.), Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), том. 10716 LNCS, Springer-Verlag GmbH and Co. KG, стр. 295-303, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Российская Федерация, 27.07.2017. https://doi.org/10.1007/978-3-319-73013-4_27

An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. / Gimadi, Edward.

Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. ред. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. стр. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS).

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

TY - GEN

T1 - An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity

AU - Gimadi, Edward

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm3) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm2.5) time.

AB - The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm3) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm2.5) time.

KW - Dynamic programming

KW - Exact algoritm

KW - Outerplanar graph

KW - Time complexity

KW - Time complexity Dynamic programming

KW - TREES

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

U2 - 10.1007/978-3-319-73013-4_27

DO - 10.1007/978-3-319-73013-4_27

M3 - Conference contribution

AN - SCOPUS:85039416451

SN - 9783319730127

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

SP - 295

EP - 303

BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers

A2 - VanDerAalst, WMP

A2 - Ignatov, DI

A2 - Khachay, M

A2 - Kuznetsov, SO

A2 - Lempitsky, null

A2 - Lomazova, IA

A2 - Loukachevitch, N

A2 - Napoli, A

A2 - Panchenko, A

A2 - Pardalos, PM

A2 - Savchenko, AV

A2 - Wasserman, S

PB - Springer-Verlag GmbH and Co. KG

T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017

Y2 - 27 July 2017 through 29 July 2017

ER -

Gimadi E. An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. В VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, редакторы, Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. стр. 295-303. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-73013-4_27