Továbbfejlesztett közelítési algoritmusok az egy süllyesztésű, nagy tömegben történő hálózat-tervezési problémákhoz ☆

Absztrakt

Tekintsünk egy adott irányítatlan G = (V, E) gráfot, amelynek nem negatív élhossza van, egy gyökércsomópontot r ∈ V, és egy D ⊆ V halmazigényt, ahol dv jelöli azokat az áramlási egységeket, amelyeknek a v a gyökér. K típusú kábeleket is kapunk, amelyek mindegyike meghatározott kapacitással és egységnyi hosszúságú költséggel rendelkezik. Az egyszeres süllyesztésű, nagy tömegben vásárolható (SSBB) probléma a kábelek olcsó beszerelését kéri a G szélén, hogy az igények egyidejűleg az root gyökhöz továbbítsák az áramlást. A problémát azon korlátozással és anélkül vizsgálják, hogy a csomópontból származó áramlásnak egyetlen utat kell követnie a gyökérig. Minden peremre nulla vagy több kábel típusú példányt telepíthetünk. Az SSBB probléma az NP -kemény. Ebben a cikkben bemutatunk egy 153,6-közelítő algoritmust az SSBB problémára javítva az előző legjobb 216-os arányt. Abban az esetben, ha az áramlás felosztható, javítjuk az előző legjobb arányt, 76,8/α K, ahol α K kisebb mint 67,94 minden K. esetében. Különösen α 2 17,7, α 3 23,2, α 4 28,8 és α 5 34,3 .

Előző kiadott cikk Következő kiadott cikk

Kulcsszavak

E cikk előzetes változata a Proc. SWAT 2004 [R. Jothi, B. Raghavachari, Továbbfejlesztett közelítési algoritmusok az egyszeres süllyesztésű, nagy tömegű hálózat tervezési problémáihoz, in: Proc. 9. skandináv műhely az algoritmuselméletről (SWAT), 2004, 336–348. [8]].

Ajánlott cikkek

Cikkeket idézve

Cikkmérők

A ScienceDirectről
Távoli hozzáférés
Bevásárlókocsi
Hirdet
Kapcsolat és támogatás
Felhasználási feltételek
Adatvédelmi irányelvek

A cookie-kat a szolgáltatásunk nyújtásában és fejlesztésében, valamint a tartalom és a hirdetések személyre szabásában segítjük. A folytatással elfogadja a sütik használata .