Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

References

• Adler M, Heeringa B (2012) Approximating optimal binary decision trees. Algorithmica 62(3–4):1112–1121.Crossref, Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Blum A, Chalasani P, Coppersmith D, Pulleyblank WR, Raghavan P, Sudan M (1994) The minimum latency problem. Thomson Leighton F, Goodrich MT, eds. Proc. 26th Annual ACM Sympos. Theory Comput., STOC ’94 (ACM, New York), 163–171.Crossref, Google Scholar
• Chakaravarthy V, Pandit V, Roy S, Sabharwal Y (2009) Approximating decision trees with multiway branches. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W, eds. Proc. 36th Internat. Colloquium Automata Languages Programming, ICALP ’09 (Springer, Berlin), 210–221.Crossref, Google Scholar
• Chakaravarthy VT, Pandit V, Roy S, Awasthi P, Mohania MK (2011) Decision trees for entity identification: Approximation algorithms and hardness results. ACM Trans. Algorithms 7(2):Article 15.Crossref, Google Scholar
• Charikar M, Chekuri C, Goel A, Guha S (1998) Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k median. Vitter JS, ed. Proc. 30th Annual ACM Sympos. Theory of Comput., STOC ’98 (ACM, New York), 114–123.Crossref, Google Scholar
• Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’03 (IEEE Computer Society, Washington, DC), 36–45.Crossref, Google Scholar
• Chekuri C, Pál M (2005) A recursive greedy algorithm for walks in directed graphs. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 245–253.Crossref, Google Scholar
• Christofides N (1977) Worst-case analysis of a new heuristic for the travelling salesman problem. GSIA, Carnegie Mellon University Report 388, Pittsburgh.Google Scholar
• Dasgupta S (2004) Analysis of a greedy active learning strategy. Adv. Neural Inform. Processing Systems (NIPS), 337–344.Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Fakcharoenphol J, Harrelson C, Rao S (2007) The k-traveling repairmen problem. ACM Trans. Algorithms 3(4):Article 40.Crossref, Google Scholar
• Fakcharoenphol J, Rao S, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. 69(3):485–497.Crossref, Google Scholar
• Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219–234.Crossref, Google Scholar
• Garey MR, Graham RL (1974) Performance bounds on the splitting algorithm for binary testing. Acta Informatica 3(4):347–355.Crossref, Google Scholar
• Garg N (1996) A 3-approximation for the minimum tree spanning k vertices. Proc. 37th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 302–309.Crossref, Google Scholar
• Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1):66–84.Crossref, Google Scholar
• Goemans M, Vondrák J (2006) Stochastic covering and adaptivity. LATIN 2006: Theoretical Informatics, Lecture Notes in Comput. Sci., Vol. 3887 (Springer, Berlin), 532–543.Crossref, Google Scholar
• Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42:427–486.Google Scholar
• Guha S, Munagala K (2009) Multi-armed bandits with metric switching costs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W, eds. Proc. 36th Internat. Colloquium Automata Languages Programming, ICALP ’09 (Springer, Berlin), 496–507.Google Scholar
• Guillory A, Bilmes J (2009) Average-case active learning with costs. Algorithmic Learning Theory (Springer, Berlin), 141–155.Crossref, Google Scholar
• Gupta A, Hajiaghayi MT, Räcke H (2006) Oblivious network design. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithm, SODA ’06 (ACM, New York), 970–979.Crossref, Google Scholar
• Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. Larmore LL, Goemans MX, eds. Proc. 35th Annual Sympos. Theory Comput., STOC ’03 (ACM, New York), 585–594.Crossref, Google Scholar
• He T, Lee K-W, Swami A (2010) Flying in the dark: Controlling autonomous data ferries with partial observations. Knightly EW, Chiasserini C-F, Lin X, eds. Proc. 11th ACM Internat. Sympos. Mobile Ad Hoc Networking Computing, MobiHoc ’09 (ACM, New York), 141–150.Crossref, Google Scholar
• Hyafil L, Rivest RL (1976/77) Constructing optimal binary decision trees is NP-complete. Inform. Processing Lett. 5(1):15–17.Crossref, Google Scholar
• Jaillet P (1988) A priori solution of a travelling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6):929–936.Link, Google Scholar
• Jia L, Lin G, Noubir G, Rajaraman R, Sundaram R (2005) Universal approximations for TSP, Steiner tree, and set cover. Kleinberg JM, ed. Proc. 37th Annual ACM Sympos. Theory Comput., STOC ’05 (ACM, New York), 386–395.Crossref, Google Scholar
• Kosaraju SR, Przytycka TM, Borgstrom RS (1999) On an optimal split tree problem. Dehne FKHA, Gupta A, Sack J-R, Tamassia R, eds. Proc. 6th Internat. Workshop Algorithms and Data Structures, WADS ’99 (Springer, Berlin), 157–168.Crossref, Google Scholar
• Liu Z, Parthasarathy S, Ranganathan A, Yang H (2008) Near-optimal algorithms for shared filter evaluation in data stream systems. Wang J, ed. Proc. ACM SIGMOD Internat. Conf. Management of Data, SIGMOD ’’08 (ACM, New York), 133–146.Crossref, Google Scholar
• Loveland DW (1985) Performance bounds for binary testing with arbitrary weights. Acta Inform. 22(1):101–114.Crossref, Google Scholar
• Munagala K, Srivastava U, Widom J (2007) Optimization of continuous queries with shared expensive filters. Libkin L, ed. Proc. 26th ACM SIGACT-SIGMOD-SIGART Sympos. Principles of Database Systems (ACM, New York), 215–224.Crossref, Google Scholar
• Nagarajan V (2009) Approximation algorithms for sequencing problems. Ph.D. thesis, Tepper School of Business, Carnegie Mellon University, Pittsburgh.Google Scholar
• Nowak RD (2011) The geometry of generalized binary search. IEEE Trans. Inform. Theory 57(12):7893–7906.Crossref, Google Scholar
• Schalekamp F, Shmoys D (2008) Algorithms for the universal and a priori TSP. Oper. Res. Lett. 36(1):1–3.Crossref, Google Scholar
• Shah RC, Roy S, Jain S, Brunette W (2003) Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks 1(2–3):215–233.Crossref, Google Scholar
• Shmoys D, Talwar K (2008) A constant approximation algorithm for the a priori traveling salesman problem. Lodi A, Panconesi A, Rinaldi G, eds. Proc. 13th Internat. Conf. Integer Programming and Combinatorial Optim., IPCO ’08 (Springer, Berlin), 331–343.Crossref, Google Scholar
• Sviridenko M (2004) A note on maximizing a submodular set function subject to knapsack constraint. Oper. Res. Lett. 32(1):41–33.Crossref, Google Scholar
• Zhao W, Ammar MH (2003) Message ferrying: Proactive routing in highly-partitioned wireless ad hoc networks. Proc. 10th IEEE Internat. Workshop Future Trends Distributed Comput. Systems, FTDCS ’04 (IEEE Computer Society, Washington, DC) 308–314.Google Scholar
• Zhao W, Ammar MH, Zegura EW (2004) A message ferrying approach for data delivery in sparse mobile ad hoc networks. Proc. 5th ACM Internat. Sympos. Mobile Ad Hoc Networking Computing, MobiHoc ’04 (ACM, New York), 187–198.Crossref, Google Scholar
• Zhao W, Ammar MH, Zegura EW (2005) Controlling the mobility of multiple data transport ferries in a delay-tolerant network. Proc. 24th Annual Joint Conf. IEEE Comput. Communications Societies, INFOCOM ’05 (IEEE Piscataway, NJ) 1407–1418.Google Scholar