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
מזהי עצם דיגיטלי (DOIs)	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, גרוזיה משך הזמן: 24 יולי 2023 → 28 יולי 2023

סדרות פרסומים

שם	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך	13967 LNCS
ISSN (מודפס)	0302-9743
ISSN (אלקטרוני)	1611-3349

כנס

כנס	Proceedings of the 19th International Conference on on Unity of Logic and Computation, CiE 2023
מדינה/אזור	גרוזיה
עיר	Batumi
תקופה	24/07/23 → 28/07/23

הערה ביבליוגרפית

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(\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, גרוזיה, 24/07/23. 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 - http://www.scopus.com/inward/record.url?scp=85172412872&partnerID=8YFLogxK

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.

תקציר

סדרות פרסומים

כנס

הערה ביבליוגרפית

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי