Vi anser att problemet med att bygga optimala beslut träd: med tanke på en samling tester som kan disambiguera mellan en uppsättning m möjliga sjukdomar, varje test har en kostnad, och a-priori sannolikheten för någon viss sjukdom, vad är en bra adaptiv strategi för att utföra dessa tester för att minimera den förväntade kostnaden för att identifiera sjukdomen? Detta problem har studerats i flera arbeten, med O(log m)-uppskattningar kända i specialfall när antingen kostnader eller sannolikheter är enhetliga. I detta dokument löser vi tillnärmningen av det allmänna problemet genom att ge en tight O(log m)-tillnärmningsalgoritm. Vi anser också att en betydande generalisering, adaptiv resande säljare problem. Med tanke på en underliggande metriska utrymme, en slumpmässig delmängd S av hörn dras från en känd distribution, men S är inledningsvis okänd-vi får information om huruvida någon vertex är i S bara när det besöks. Vad är en bra adaptiv strategi för att besöka alla hörn i slumpmässiga delmängd S medan minimera den förväntade avstånd rest? Detta problem har tillämpningar i routing meddelande färjor i ad-hoc nätverk, och även modeller växla kostnader mellan tester i det optimala beslut träd problem. Vi ger en poly-logaritmisk approximationsalgoritm för adaptiv TSP, vilket är nästan bäst möjligt på grund av en koppling till den välkända gruppen Steiner träd problem. Slutligen anser vi den relaterade adaptiv resande reparatör problem, där målet är att beräkna en adaptiv tur minimera den förväntade summan av ankomsttider hörn i den slumpmässiga delmängd S; vi får en poly-logaritmisk approximation algoritm för detta problem också.
IPP är nära relaterat till adaptiv resande säljare problem (ATSP) REF.
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}