-
Fair allocation algorithms for indivisible items under structured conflict constraintsChiarelli, 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).Source: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, iss. 7, [article no.] 302, Oct. 2023, 21 str.)Type of material - article, component part ; adult, seriousPublish date - 2023Language - englishCOBISS.SI-ID - 164733443
Author
Chiarelli, Nina |
Krnc, Matjaž, 1987- |
Milanič, Martin, 1980- |
Pferschy, Ulrich |
Schauer, Joachim
Topics
pravična delitev |
konfliktni grafi |
delno barvanje |
konveksni dvodelni grafi |
omejeno klična širina |
omejeno drevesno neodvisnostno število |
fair division |
conflict graphs |
partial coloring |
convex bipartite graphs |
bounded clique-width |
bounded tree-independence number
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Chiarelli, Nina | 35452 |
Krnc, Matjaž, 1987- | 34562 |
Milanič, Martin, 1980- | 30211 |
Pferschy, Ulrich | ![]() |
Schauer, Joachim | ![]() |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.