Abstrakt. För en given graf G med positiv integral kostnad och fördröjning på kanter, distinkta hörn s och t, kostnadsbunden C  på Z + och fördröjningsbunden D på Z +, k bi-konstraint sökväg (kBCP) problem är att beräkna k separerade st-vägar under C och D. Detta problem är känt NP-hård, även när k = 1 [4]. Detta dokument ger först en enkel approximationsalgoritm med faktor-(2, 2), dvs. algoritmen beräknar en lösning med fördröjning och kostnad som begränsas av 2 * D respektive 2 * C. Senare, en ny förbättrad approximation algoritm med förhållandet (1 + β, max{2, 1 + ln utvecklas genom att bygga intressanta extra grafer och använda cykeln annulleringsmetod. Som en följd av detta kan vi få en faktor-(1.369, 2) approximationsalgoritm genom att ställa in 1 + ln 1 β = 2 och en faktor-(1.567, 1.567) algoritm genom att ställa in 1 + β = 1 + ln 1 β. Dessutom, genom att ställa in β = 0, en approximationsalgoritm med förhållande (1, O(ln n)), dvs. En algoritm med endast ett faktorförhållande O (ln n) på kostnaden kan omedelbart erhållas. Såvitt vi vet är detta den första icke-triviala approximationsalgoritmen för problemet med kBCP som strikt lyder fördröjningsbegränsningen.
Ett närbesläktat problem, det k osammanhängande bikonsekterade stigproblemet (kBCP), mål k osammanhängande st-patter som uppfyller den givna kostnadsbegränsningen ) eller ett enda faktorförhållande av O (ln n) (dvs. Förhållandet mellan bifaktor och approximation (1, O(ln n)) har utvecklats för allmänt k i REF, där β > 0 är ett fast positivt reellt tal.
Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}