Överväg ett nätverk design ansökan där vi vill lägga ner en minimikostnad spänner träd i en given graf; men vi har bara stokastisk information om kantkostnader. För att få reda på den exakta kostnaden för varje kant, måste vi genomföra en studie som ådrar sig ett pris. Vårt mål är att hitta ett spänt träd samtidigt minimera vannyttan, vilket är summan av trädkostnaden och det totala priset som vi spenderar på studierna. I olika applikationer ger varje kant ett stokastiskt belöningsvärde. Vårt mål är att hitta en spännande träd samtidigt maximera nyttan, vilket är träd belöning minus de priser som vi betalar. Situationer som ovan två uppstår ofta i praktiken där vi vill hitta en bra lösning på ett optimeringsproblem, men vi börjar med bara en del kunskap om parametrarna för problemet. Den saknade informationen kan endast hittas efter att ha betalat ett bevispris, som vi kallar priset på information. Vilken strategi bör vi anta för att optimera vår förväntade nytta / missbruk? Ett klassiskt exempel på ovanstående inställning är Weitzmans "pandoras box" problem där vi ges sannolikhetsfördelningar på värden av n oberoende slumpvariabler. Målet är att välja en enda variabel med ett stort värde, men vi kan hitta de faktiska resultaten först efter att ha betalat ett pris. Vårt arbete är en generalisering av denna modell till andra kombinatoriska optimeringsproblem såsom matchning, set cover, anläggning plats, och prissamla Steiner träd. Vi ger en teknik som minskar sådana problem till deras icke-pris motsvarigheter, och använder den för att utforma exakta / approximation algoritmer för att optimera vår nytta / missbruk. Våra tekniker sträcker sig till situationer där det finns ytterligare begränsningar för vilka parametrar som kan sonderas eller när vi samtidigt kan sondera en delmängd av parametrarna. * En del av detta arbete gjordes medan författarna besökte Simons Institute for the Theory of Computing. Vi är tacksamma till Anupam Gupta och Viswanath Nagarajan för flera diskussioner om detta projekt.
Singla REF generaliserade denna modell till andra kombinatoriska optimeringsproblem såsom matchning, set cover, anläggning plats, och erhållna approximation algoritmer.
The Price of Information in Combinatorial Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}