Exact and Approximation Algorithms for the Expanding Search Problem

References

• Afrati F, Cosmadakis S, Papadimitriou CH, Papageorgiou G, Papakostantinou N (1986) The complexity of the travelling repairman problem. RAIRO Theor. Inform. Appl. 20(1):79–87.Crossref, Google Scholar
• Alpern S, Gal S (2003) The Theory of Search Games and Rendezvous (Kluwer, Dordrecht, Netherlands).Google Scholar
• Alpern S, Lidbetter T (2013) Mining coal or finding terrorists: The expanding search paradigm. Oper. Res. 61(2):265–279.Link, Google Scholar
• Alpern S, Lidbetter T (2019) Approximate solutions for expanding search games on general networks. Ann. Oper. Res. 275(2):259–279.Crossref, Google Scholar
• Alpern S, Fokkink R, Gasieniec L, Lindelauf R, Subrahmanian V, eds. (2013) Search Theory: A Game Theoretic Perspective (Springer, New York).Crossref, Google Scholar
• Angelopoulos S, Dürr C, Lidbetter T (2019) The expanding search ratio of a graph. Discrete Appl. Math. 260:51–65.Crossref, Google Scholar
• Archer A, Levin A, Williamson DP (2008) A faster, better approximation algorithm for the minimum latency problem. SIAM J. Comput. 37(5):1472–1498.Crossref, Google Scholar
• Ausiello G, Leonardi S, Marchetti-Spaccamela A (2000) On salesmen, repairmen, spiders, and other traveling agents. Bongiovanni G, Petreschi R, Gambosi G, eds. Italian Conf. Algorithms Complexity, Lecture Notes in Computer Science, vol. 1767 (Springer, Berlin), 1–16.Google Scholar
• Averbakh I (2012) Emergency path restoration problems. Discrete Optim. 9(1):58–64.Crossref, Google Scholar
• Averbakh I, Pereira J (2012) The flowtime network construction problem. IIE Trans. 44(8):681–694.Crossref, Google Scholar
• Averbakh I, Pereira J (2018) Lateness minimization in pairwise connectivity restoration problems. INFORMS J. Comput. 30(3):522–538.Link, Google Scholar
• Averbakh I, Pereira J (2020) Tree optimization based heuristics and metaheuristics in network construction problems. Preprint, submitted July 3, https://arxiv.org/abs/2007.03425.Google Scholar
• Bulhoes T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93:66–78.Crossref, Google Scholar
• Carlson J, Eppstein D (2006) The weighted maximum-mean subtree and other bicriterion subtree problems. Arge L, Freivalds R, eds. Scand. Workshop Algorithm Theor. SWAT 2006, Lecture Notes in Computer Science, vol. 4059 (Springer, Berlin), 400–410.Google Scholar
• Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. Proc. 44th Annu. IEEE Sympos. Foundations Comput. Sci. 2003 (IEEE, Piscataway, NJ), 36–45.Google Scholar
• Chekuri C, Motwani R, Natarajan B, Stein C (2001) Approximation techniques for average completion time scheduling. SIAM J. Comput. 31(1):146–166.Crossref, Google Scholar
• Correa JR, Fernandes CG, Wakabayashi Y (2010) Approximating a class of combinatorial problems with rational objective function. Math. Program. 124(1-2):255–269.Crossref, Google Scholar
• Correa JR, Schulz AS (2005) Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4):1005–1021.Link, Google Scholar
• Erdős P, Rényi A (1959) On random graphs. I. Publicationes Mathematicae 6(290-297):18.Google Scholar
• Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219–234.Crossref, Google Scholar
• Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper. Res. 41(6):1055–1064.Link, Google Scholar
• Fokkink R, Lidbetter T, Végh LA (2019) On submodular search and machine scheduling. Math. Oper. Res. 44(4):1431–1449.Link, Google Scholar
• Ford LR, Fulkerson DR (1956) Maximal flow through a network. Canad. J. Math. 8:399–404.Crossref, Google Scholar
• Gillies DW, Liu JWS (1995) Scheduling tasks with AND/OR precedence constraints. SIAM J. Comput. 24(4):797–810.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• Goldberg AV (1984) Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley.Google Scholar
• Goldberg AV, Tarjan RE (1988) A new approach to the maximum-flow problem. J. ACM 35(4):921–940.Crossref, Google Scholar
• Happach F, Hellerstein L, Lidbetter T (2020) A general framework for approximating min sum ordering problems. Preprint, submitted April 13, https://arxiv.org/abs/2004.05954.Google Scholar
• Hegde C, Indyk P, Schmidt L (2015) A nearly-linear time framework for graph-structured sparsity. Kambhampati S, ed. Proc. 32nd Internat. Conf. Machine Learning (JMLR, Palo Alto, CA), 928–937.Google Scholar
• Hellerstein L, Lidbetter T, Pirutinsky D (2019) Solving zero-sum games using best-response oracles with applications to search games. Oper. Res. 67(3):731–743.Link, Google Scholar
• Hermans B, Leus R, Matuschke J (2019) Exact and approximation algorithms for the expanding search problem. Preprint, submitted November 20, https://arxiv.org/abs/1911.08959.</prpt>Google Scholar
• Kao MJ, Katz B, Krug M, Lee D, Rutter I, Wagner D (2013) The density maximization problem in graphs. J. Comb. Optim. 26(4):723–754.Crossref, Google Scholar
• Khuller S, Saha B (2009) On finding dense subgraphs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Internat. Colloq. Automata Languages Program., Lecture Notes in Computer Science, vol. 5555 (Springer, Berlin), 597–608.Google Scholar
• Klau GW, Ljubić I, Mutzel P, Pferschy U, Weiskircher R (2003) The fractional prize-collecting Steiner tree problem on trees. Di Battista G, Zwick U, eds. Eur. Sympos. Algorithms ESA 2003, Lecture Notes in Computer Science, vol. 2832 (Springer, Berlin), 691–702 .Google Scholar
• Klein PN, Ravi R (1995) A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1):104–115.Crossref, Google Scholar
• Koopman BO (1956a) The theory of search I: Kinematic bases. Oper. Res. 4(3):324–346.Link, Google Scholar
• Koopman BO (1956b) The theory of search II: Target detection. Oper. Res. 4(5):503–531.Link, Google Scholar
• Koopman BO (1957) The theory of search III: The optimum distribution of searching effort. Oper. Res. 5(5):613–626.Link, Google Scholar
• Koutsoupias E, Papadimitriou C, Yannakakis M (1996) Searching a fixed graph. Meyer F, Monien B, eds. Automata Languages Program. ICALP 1996, Lecture Notes in Computer Science, vol. 1099 (Springer, Berlin), 280–289.Crossref, Google Scholar
• Lau HC, Ngo TH, Nguyen BN (2006) Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics. Discrete Optim. 3(4):385–391.Crossref, Google Scholar
• Lee VE, Ruan N, Jin R, Aggarwal C (2010) A survey of algorithms for dense subgraph discovery. Aggarwal C, Wang H, eds. Managing and Mining Graph Data, Advances in Database Systems, vol. 40 (Springer, Boston), 303–336.Crossref, Google Scholar
• Leibovich E (2009) Approximating graph density problems. Unpublished master’s thesis, Open University of Israel, Raanana, Israel.Google Scholar
• Li S, Huang S (2018) Multiple searchers searching for a randomly distributed immobile target on a unit network. Networks 71(1):60–80.Crossref, Google Scholar
• Magnanti TL, Wolsey LA (1995) Optimal trees. Ball MO, Magnanti TL, Monma CL, Nemhauser GL, eds. Network Models, Handbooks in Operations Research and Management Science, vol. 7 (Elsevier, Amsterdam), 503–615.Google Scholar
• Méndez-Díaz I, Zabala P, Lucena A (2008) A new formulation for the traveling deliveryman problem. Discrete Appl. Math. 156(17):3223–3237.Crossref, Google Scholar
• Monma CL, Sidney JB (1979) Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4(3):215–224.Link, Google Scholar
• Orlin JB, Punnen AP, Schulz AS (2004) Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5):1201–1214.Crossref, Google Scholar
• Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576–590.Link, Google Scholar
• Potts CN (1980) An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Studies. 13:78–87.Crossref, Google Scholar
• Queyranne M, Wang Y (1991) Single-machine scheduling polyhedra with precedence constraints. Math. Oper. Res. 16(1):1–20.Link, Google Scholar
• Sidney JB (1975) Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2):283–298.Link, Google Scholar
• Sitters R (2002) The minimum latency problem is NP-hard for weighted trees. Cook WJ, Schulz AS, eds. Internat. Conf. Integer Program. Combinatorial Optim. IPCO 2002, Lecture Notes in Computer Science, vol. 2337 (Springer, Berlin), 230–239.Google Scholar
• Smith WE (1956) Various optimizers for single-stage production. Nav. Res. Logist. Quart. 3(1-2):59–66.Crossref, Google Scholar
• Stone LD (2007) Theory of Optimal Search, 2nd ed. (INFORMS, Catonsville, MD).Google Scholar
• Stone LD, Royset JO, Washburn AR (2016) Optimal Search for Moving Targets (Springer, Cham, Switzerland).Crossref, Google Scholar
• Tan Y, Qiu F, Das AK, Kirschen DS, Arabshahi P, Wang J (2019) Scheduling post-disaster repairs in electricity distribution networks. IEEE Trans. Power Systems 34(4):2611–2621.Crossref, Google Scholar
• Trummel K, Weisinger J (1986) The complexity of the optimal searcher path problem. Oper. Res. 34(2):324–327.Link, Google Scholar