تخطي إلى التنقل الرئيسي تخطي إلى البحث تخطي إلى المحتوى الرئيسي

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

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

ملخص

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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفCiE
المحررونGianluca Della Vedova, Besik Dundua, Steffen Lempp, Florin Manea
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات287-296
عدد الصفحات10
رقم المعيار الدولي للكتب (المطبوع)9783031369773
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!ConferenceProceedings 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.

بصمة

أدرس بدقة موضوعات البحث “An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا