VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Fair allocation algorithms for indivisible items under structured conflict constraints
    Chiarelli, Nina ...
    V članku obravnavamo pravično dodelitev nedeljivih dobrin več agentom z dodatnimi konfliktnimi omejitvami. Te so predstavljene z grafom konfliktov, kjer vsaka dobrina ustreza točki grafa, povezave v ... grafu pa predstavljajo nezdružljive pare dobrin, ki jih ne smemo dodeliti istemu agentu. Problem je hkratna posplošitev znanih problemov PARTICIJA in NEODVISNA MNOŽICA; dopustna rešitev pa ustreza delnemu barvanju konfliktnega grafa. V nastalem optimizacijskem problemu ima vsak agent svojo funkcijo za vrednotenje dobrin, cilj pa je maksimizacija najnižje skupne vrednosti dobrin, dodeljenih kateremu koli od agentov. V prejšnjem prispevku se je izkazalo, da je ta problem krepko NP-težek za več dobro znanih razredov grafov, npr. za dvodelne grafe in njihove povezavne grafe. Po drugi strani pa je bilo dokazano, da obstajajo algoritmi psevdopolinomske časovne zahtevnosti za razrede tetivnih grafov, neprimerljivostnih grafov, bikonveksnih dvodelnih grafov in grafov omejene drevesne širine. V tem prispevku nadaljujemo s tovrstnimi raziskavami in razvijemo psevdopolinomske algoritme, ki problem rešijo za razred konveksnih dvodelnih konfliktnih grafov, grafe omejene klične širine in grafe omejenega drevesnega neodvisnostnega števila. Algoritmi temeljijo na dinamičnem programiranju in omogočajo tudi popolnoma polinomske aproksimacijske sheme (FPTAS).
    Vir: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, iss. 7, [article no.] 302, Oct. 2023, 21 str.)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 164733443

    Povezava(-e):

    https://link.springer.com/article/10.1007/s40314-023-02437-0
    DOI

vir: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, iss. 7, [article no.] 302, Oct. 2023, 21 str.)
loading ...
loading ...
loading ...

Vnos na polico