Резюме

Да разгледаме дадена ненасочена графика G = (V, E) с неотрицателни дължини на ръбове, корен възел r ∈ V и набор D ⊆ V от искания с dv, представляващи мерните единици на потока, които искането v ∈ D иска да изпрати на коренът. Също така ни се дават K вида кабели, всеки с определен капацитет и цена на единица дължина. Проблемът с единична мивка за купуване (SSBB) изисква евтина инсталация на кабели по краищата на G, така че изискванията могат едновременно да изпращат своя поток към root r. Проблемът се изучава с и без ограничението, че потокът от възел трябва да следва един път към корена. Разрешено ни е да инсталираме нула или повече копия от тип кабел на всеки ръб. Проблемът на SSBB е NP-твърд. В тази статия представяме алгоритъм за приближение 153,6 за проблема SSBB, подобряващ предишното най-добро съотношение от 216. За случая, в който потокът се разделя, подобряваме предишното най-добро съотношение от 76,8 към α K, където α K е по-малко от 67,94 за всички К. По-специално, α 2 17,7, α 3 23,2, α 4 28,8 и α 5 34,3 .

сближаване

Предишен статия в бр Следващия статия в бр

Ключови думи

Предварителната версия на тази статия се появи в Proc. SWAT 2004 [R. Jothi, B. Raghavachari, Подобрени алгоритми за сближаване на проблемите с дизайна на мрежата с единична мивка, в: Proc. 9-та скандинавска работилница по теория на алгоритъма (SWAT), 2004, стр. 336–348. [8]].

Препоръчани статии

Позоваване на статии

Статия Метрики

  • За ScienceDirect
  • Отдалечен достъп
  • Карта за пазаруване
  • Рекламирайте
  • Контакт и поддръжка
  • Правила и условия
  • Политика за поверителност

Използваме бисквитки, за да помогнем да предоставим и подобрим нашата услуга и да приспособим съдържанието и рекламите. Продължавайки, вие се съгласявате с използване на бисквитки .