Vi anser en klass av problem där en algoritm försöker beräkna en funktion f över en uppsättning n ingångar, där varje indata har ett tillhörande pris. Algoritmen frågar ingångar sekventiellt, försöker lära sig värdet av funktionen för den lägsta kostnaden. Vi en p l y t h e konkurrensanalys av algoritmer till detta ramverk, utforma algoritmer som ådrar sig stora kostnader endast när kostnaden för den billigaste \proof "för värdet av f är också stor. Vi p r o e algoritmer som uppnår det optimala konkurrensförhållandet för funktioner som inkluderar godtyckliga booleska och/eller träd, och för problemet med att söka i en sorterad array. W e också undersöka en modell för prissättning inom denna ram och bygga, för varje AND / OR träd, en uppsättning priser som satis es en mycket stark typ av jämvikt egendom.
Att beräkna en funktion över indata studeras inom ramen för booleska och / eller träd REF, där källdata är korrekt och varje indata har ett tillhörande pris.
Query Strategies for Priced Information
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Computer Science']}