Abstrakt. Vi studerar ett optimeringsproblem som uppstår i samband med dataplacering i ett multimedialagringssystem. Vi ges en samling av M multimedia objekt (data objekt) som måste tilldelas ett lagringssystem som består av N disks d 1, d 2..., d N. Vi ges också uppsättningar U 1, U 2,. .., U M sådan att U i är den uppsättning kunder som söker ith data objekt. Varje disk d j kännetecknas av två parametrar, nämligen dess lagringskapacitet C j som anger det maximala antalet dataobjekt som kan tilldelas den, och en lastkapacitet L j som anger det maximala antalet kunder som den kan tjäna. Målet är att hitta en placering av dataobjekt till diskar och en tilldelning av kunder till diskar för att maximera det totala antalet kunder, med förbehåll för lagringssystemets kapacitetsbegränsningar. Vi studerar detta dataplaceringsproblem för två naturliga klasser av lagringssystem, nämligen homogent och enhetligt förhållande. Vi visar att en algoritm utvecklad av Shachnai och Tamir Thurimella, Institutionen för datavetenskap, University of Denver, CO, e-post: ramki@cs.du.edu; A. Zhu, e-post: Google Inc., Mountain View, CA 94043; anzhu@cs.stanford.edu. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från Publications Department., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (dataplacering uppnår bästa möjliga absolut gräns för antalet kunder som alltid kan vara nöjda. Vi visar också hur man implementerar algoritmen så att den har en körtid av O((N + M) log (N + M) ). Dessutom utformar vi en polynom-tid approximation system, lösa ett öppet problem som finns i samma papper.
I REF, författarna använder en polynom tid approximation schema för dataplacering problem i homogena och enhetliga kvot lagringssystem.
Approximation algorithms for data placement on parallel disks
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science']}