An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.

Zeev Nutov

doi:10.1007/978-3-031-36978-0_23

An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.

Zeev Nutov

מדעי המחשב

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

ملخص

In minimum power network design problems we are given an undirected graph G= (V, E) with edge costs { c_e: e∈ E}. The goal is to find an edge set F⊆ E that satisfies a prescribed property of minimum power pc(F)=∑v∈Vmax{ce:e∈Fisincidenttov}. In the Min-Power k Edge Disjoint st -Paths problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question whether it admits an approximation ratio sublinear in k even for unit costs. We give a 42k -approximation algorithm for general costs.

اللغة الأصلية	الإنجليزيّة
عنوان منشور المضيف	CiE
المحررون	Gianluca Della Vedova, Besik Dundua, Steffen Lempp, Florin Manea
ناشر	Springer Science and Business Media Deutschland GmbH
الصفحات	287-296
عدد الصفحات	10
رقم المعيار الدولي للكتب (المطبوع)	9783031369773
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/978-3-031-36978-0_23
حالة النشر	نُشِر - 2023
الحدث	Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023 - Batumi, غروزيا المدة: ٢٤ يوليو ٢٠٢٣ → ٢٨ يوليو ٢٠٢٣

سلسلة المنشورات

الاسم	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت	13967 LNCS
رقم المعيار الدولي للدوريات (المطبوع)	0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)	1611-3349

!!Conference

!!Conference	Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023
الدولة/الإقليم	غروزيا
المدينة	Batumi
المدة	٢٤/٠٧/٢٣ → ٢٨/٠٧/٢٣

ملاحظة ببليوغرافية

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

الوصول إلى المستند

10.1007/978-3-031-36978-0_23

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

Nutov, Z. (2023). An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths. في G. Della Vedova, B. Dundua, S. Lempp, & F. Manea (المحررون), CiE (الصفحات 287-296). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 13967 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-36978-0_23

Nutov, Zeev. / An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths. CiE. محرر / Gianluca Della Vedova ; Besik Dundua ; Steffen Lempp ; Florin Manea. Springer Science and Business Media Deutschland GmbH, 2023. الصفحات 287-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bbce660d358f4aa09eea8177504d3e12,

title = "An \$O(\textbackslash{}sqrt\{k\})\$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.",

abstract = "In minimum power network design problems we are given an undirected graph G= (V, E) with edge costs \{ ce: e∈ E\}. The goal is to find an edge set F⊆ E that satisfies a prescribed property of minimum power pc(F)=∑v∈Vmax\{ce:e∈Fisincidenttov\}. In the Min-Power k Edge Disjoint st -Paths problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question whether it admits an approximation ratio sublinear in k even for unit costs. We give a 42k -approximation algorithm for general costs.",

keywords = "edge disjoint st-paths, minimum power, wireless networks",

author = "Zeev Nutov",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023 ; Conference date: 24-07-2023 Through 28-07-2023",

year = "2023",

doi = "10.1007/978-3-031-36978-0\_23",

language = "אנגלית",

isbn = "9783031369773",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "287--296",

editor = "\{Della Vedova\}, Gianluca and Besik Dundua and Steffen Lempp and Florin Manea",

booktitle = "CiE",

address = "גרמניה",

}

Nutov, Z 2023, An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths. في G Della Vedova, B Dundua, S Lempp & F Manea (المحررون), CiE. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), المجلد 13967 LNCS, Springer Science and Business Media Deutschland GmbH, الصفحات 287-296, Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023, Batumi, غروزيا, ٢٤/٠٧/٢٣. https://doi.org/10.1007/978-3-031-36978-0_23

An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths. / Nutov, Zeev.
CiE. محرر / Gianluca Della Vedova; Besik Dundua; Steffen Lempp; Florin Manea. Springer Science and Business Media Deutschland GmbH, 2023. صفحة 287-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 13967 LNCS).

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

TY - GEN

T1 - An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.

AU - Nutov, Zeev

PY - 2023

Y1 - 2023

N2 - In minimum power network design problems we are given an undirected graph G= (V, E) with edge costs { ce: e∈ E}. The goal is to find an edge set F⊆ E that satisfies a prescribed property of minimum power pc(F)=∑v∈Vmax{ce:e∈Fisincidenttov}. In the Min-Power k Edge Disjoint st -Paths problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question whether it admits an approximation ratio sublinear in k even for unit costs. We give a 42k -approximation algorithm for general costs.

AB - In minimum power network design problems we are given an undirected graph G= (V, E) with edge costs { ce: e∈ E}. The goal is to find an edge set F⊆ E that satisfies a prescribed property of minimum power pc(F)=∑v∈Vmax{ce:e∈Fisincidenttov}. In the Min-Power k Edge Disjoint st -Paths problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question whether it admits an approximation ratio sublinear in k even for unit costs. We give a 42k -approximation algorithm for general costs.

KW - edge disjoint st-paths

KW - minimum power

KW - wireless networks

UR - https://www.scopus.com/pages/publications/85172412872

U2 - 10.1007/978-3-031-36978-0_23

DO - 10.1007/978-3-031-36978-0_23

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:85172412872

SN - 9783031369773

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

SP - 287

EP - 296

BT - CiE

A2 - Della Vedova, Gianluca

A2 - Dundua, Besik

A2 - Lempp, Steffen

A2 - Manea, Florin

PB - Springer Science and Business Media Deutschland GmbH

T2 - Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023

Y2 - 24 July 2023 through 28 July 2023

ER -

Nutov Z. An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths. في Della Vedova G, Dundua B, Lempp S, Manea F, المحررون, CiE. Springer Science and Business Media Deutschland GmbH. 2023. صفحة 287-296. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-36978-0_23

An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.

ملخص

سلسلة المنشورات

!!Conference

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا