I flera nya tekniker för datorminne (huvudminne) är kostnaden för läsning betydligt lägre än kostnaden för att skriva. Sådan asymmetri i minneskostnader utgör en fundamentalt annorlunda modell än RAM för algoritmkonstruktion. I detta dokument studerar vi lägre och övre gränser för olika problem under sådana asymmetriska läs- och skrivkostnader. Vi betraktar både fallet där alla utom O(1) minne har asymmetrisk kostnad, och fallet med en liten cache av symmetriskt minne. Vi modellerar båda fallen med hjälp av (M)-ARAM, där det finns ett litet (symmetriskt) minne av storlek M och ett stort obundet (asymmetriskt) minne, både slumpmässig åtkomst, och där läsning från det stora minnet har enhetskostnad, men skrift har kostat 1. För FFT- och sorteringsnätverk visar vi en lägre bunden kostnad för  och/eller log, vilket tyder på att det inte är möjligt att uppnå asymptotiska förbättringar med billigare avläsningar när det är avgränsat av ett polynom i M. Dessutom finns det ett asymptotiskt gap (av min(-, log n)/logg(-M)) mellan kostnaden för sorteringsnätverk och jämförelsesortering i modellen. Detta står i kontrast till RAM-minnet och de flesta andra modeller, där de asymptotiska kostnaderna är desamma. Vi visar också en lägre gräns för beräkningar på en n × n diamant DAG av  och 2 /M ) kostnad, vilket tyder på att ingen asymptotisk förbättring kan uppnås med snabba avläsningar. Vi visar dock att för den minsta redigeringen avståndsproblem (och relaterade problem), som verkar vara en diamant DAG, kan vi slå denna lägre gräns med en algoritm med endast O(en 2 /(M min( en/3, M 1/2 ))) kostnad. För att uppnå detta använder vi en "stigskiss"-teknik som är förbjuden i en strikt DAG-beräkning. Slutligen visar vi flera intressanta övre gränser för kortaste stigproblem, minsta spännvidd och andra problem. Ett vanligt tema i många av de övre gränserna är att de kräver överflödig beräkning och en kompromiss mellan läsning och skrivande.
Sekventiella algoritmer analyseras med hjälp av Asymmetrisk RAM-modell REF, bestående av ett oändligt stort asymmetriskt minne och ett litet symmetriskt minne.
Efficient Algorithms with Asymmetric Read and Write Costs
{'venue': 'ESA 2016', 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}