On Submodular Search and Machine Scheduling

References

• [1] Adolphson D (1977) Single machine job sequencing with precedence constraints. SIAM J. Comput. 6(1):40–54.Crossref, Google Scholar
• [2] Alpern S, Gal S (2003) The Theory of Search Games and Rendezvous. Price CC, ed. Kluwer International Series in Operations Research and Management Sciences, vol. 55 (Kluwer, Boston).Google Scholar
• [3] Alpern S, Howard JV (2000) Alternating search at two locations. Dynam. Control 10(4):319–339.Crossref, Google Scholar
• [4] Alpern S, Lidbetter T (2013) Mining coal or finding terrorists: The expanding search paradigm. Oper. Res. 61(2):265–279.Link, Google Scholar
• [5] Alpern S, Lidbetter T (2014) Searching a variable speed network. Math. Oper. Res. 39(3):697–711.Link, Google Scholar
• [6] Ambühl C, Mastrolili M (2009) Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4):488–503.Crossref, Google Scholar
• [7] Ambühl C, Mastrolili M, Mutsanas N, Svensson O (2011) On the approximability of single-machine scheduling with precedence constraints. Math. Oper. Res. 36(4):653–669.Link, Google Scholar
• [8] Ambühl C, Mastrolili M, Svensson O (2007) Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Washington, DC), 329–337.Crossref, Google Scholar
• [9] Bansal N, Khot S (2009) Optimal long code test with one free bit. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Washington, DC), 453–462.Crossref, Google Scholar
• [10] Bansal N, Dürr C, Thang NK, Vásquez ÓC (2016) The local-global conjecture for scheduling with non-linear cost. J. Scheduling 20(3):239–254.Crossref, Google Scholar
• [11] Bellman R (1957) Dynamic Programming (Princeton University Press, Princeton, NJ).Google Scholar
• [12] Chekuri C, Motwani R (1999) Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1):29–38.Crossref, Google Scholar
• [13] Chudak FA, Hochbaum DS (1999) A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5):199–204.Crossref, Google Scholar
• [14] Conforti M, Cornuéjols G (1984) Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3):251–274.Crossref, Google Scholar
• [15] Correa JR, Schulz AS (2005) Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4):1005–1021.Link, Google Scholar
• [16] Cunningham W (1983) Decomposition of submodular functions. Combinatorica 3(1):53–68.Crossref, Google Scholar
• [17] Dürr C, Jeż Ł, Vásquez ÓC (2015) Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption. Discrete Appl. Math. 196(December):20–27.Crossref, Google Scholar
• [18] Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy R, Hanani H, Sauer N, Schönheim J, eds. Combinatorial Structures and Their Applications (Gordon and Breach, New York), 69–87.Google Scholar
• [19] Fokkink R, Ramsey D, Kikuta K (2016) The search value of a set. Ann. Oper. Res. 256(1):1–11.Google Scholar
• [20] Fujishige S, ed. (2005) Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58 (Elsevier, Amsterdam).Google Scholar
• [21] Gal S (1980) Search Games (Academic Press, New York).Google Scholar
• [22] Gal S (2011) Search games. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• [23] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco).Google Scholar
• [24] Gittins JC, Glazebrook K, Weber RR (2011) Multi-Armed Bandit Allocation Indices, 2nd ed. (Wiley, New York).Crossref, Google Scholar
• [25] Gluss B (1959) An optimum policy for detecting a fault in a complex system. Oper. Res. 7(4):468–477.Link, Google Scholar
• [26] Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line algorithms. Math. Oper. Res. 22(3):513–544.Link, Google Scholar
• [27] Held M, Karp RM (1962) A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math. 10(1):196–210.Crossref, Google Scholar
• [28] Höhn W, Jacobs T (2015) On the performance of Smith’s rule in single-machine scheduling with nonlinear cost. ACM Trans. Algorithms 11(4):25.Crossref, Google Scholar
• [29] Iwata S, Murota K, Shigeno M (1997) A fast parametric submodular intersection algorithm for strong map sequences. Math. Oper. Res. 22(4):803–813.Link, Google Scholar
• [30] Iwata S, Tetali P, Tripathi P (2012). Approximating minimum linear ordering problems. Gupta A, Jansen K, Rolim J, Servedio R, eds. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Lecture Notes in Computer Science, vol. 7408 (Springer, Berlin), 206–217.Crossref, Google Scholar
• [31] Lawler EL (1978) Sequencing jobs to minimize total weighted completion time. Ann. Discrete Math. 2:75–90.Crossref, Google Scholar
• [32] Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: Algorithms and complexity. Graves SC, Rinnooy Kan AHG, Zipkin PH, eds. Handbooks in Operations Research and Management Science, vol. 4 (Elsevier, Amsterdam), 445–522.Google Scholar
• [33] Lidbetter T (2013) Search games with multiple hidden objects. SIAM J. Control Optim. 51(4):3056–3074.Crossref, Google Scholar
• [34] Margot F, Queyranne M, Wang Y (2003) Decompositions, network flows and a precedence constrained single machine scheduling problem. Oper. Res. 51(6):981–992.Link, Google Scholar
• [35] Matula D (1964) A periodic optimal search. Amer. Math. Monthly 71(1):15–21.Crossref, Google Scholar
• [36] Megiddo N, Hakimi SL, Garey MR, Johnson DS, Papadimitriou CH (1988) The complexity of searching a graph. J. ACM 35(1):18–44.Crossref, Google Scholar
• [37] Megow N, Verschae J (2018) Dual techniques for scheduling on a machine with varying speed. SIAM J. Discrete Math. 32(3):1541–1571.Crossref, Google Scholar
• [38] Mitten LG (1960) An analytic solution to the least cost testing sequence problem. J. Indust. Engrg. 11(1):17–33.Google Scholar
• [39] Monma CL, Sidney JB (1979) Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4(3):215–224.Link, Google Scholar
• [40] Pisaruk NN (1992) The boundaries of submodular functions. Comput. Math. Math. Phys. 32(12):1769–1783.Google Scholar
• [41] Pisaruk NN (2003) A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time. Discrete Appl. Math. 131(3):655–663.Crossref, Google Scholar
• [42] Queyranne M (1998) Minimizing symmetric submodular functions. Math. Programming 82(1–2):3–12.Crossref, Google Scholar
• [43] Rothkopf MH (1966) Scheduling independent tasks on parallel processors. Management Sci. 12(5):437–447.Link, Google Scholar
• [44] Schrijver A (2003) Combinatorial Optimization, Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24 (Springer, Berlin).Google Scholar
• [45] Schulz AS (1996) Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Cunningham WH, McCormick ST, Queyranne M, eds. Proc. 5th Internat. Conf. Integer Programming Combin. Optimization (Springer-Verlag, Heidelberg), 301–315.Crossref, Google Scholar
• [46] Schulz AS, Verschae J (2016) Min-sum scheduling under precedence constraints. Sankowski P, Zaroliagis C, eds. Proc. 24th Annual Eur. Sympos. Algorithms, Leibniz International Proceedings in Informatics, vol. 57 (Schloss Dagstuh–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 74:1–74:13.Google Scholar
• [47] Sidney JB (1975) Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2):283–298.Link, Google Scholar
• [48] Sidney JB, Steiner G (1986) Optimal sequencing by modular decomposition: Polynomial algorithms. Oper. Res 34(4):606–612.Link, Google Scholar
• [49] Smith WE (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1–2):59–66.Crossref, Google Scholar
• [50] Stiller S, Wiese A (2010) Increasing speed scheduling and flow scheduling. Cheong O, Chwa KY, Park K, eds. Algorithms and Computation, Lecture Notes in Computer Science, vol. 6507 (Springer, Berlin), 279–290.Crossref, Google Scholar
• [51] Vöcking B (2007) Selfish load balancing. Nisam N, Roughgarden T, Tardos É, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 517–542.Crossref, Google Scholar
• [52] von Neumann J, Morgenstern O (2007) Theory of Games and Economic Behavior (Princeton University Press, Princeton, NJ).Google Scholar
• [53] von Stengel B, Werchner R (1997) Complexity of searching an immobile hider in a graph. Discrete Appl. Math. 78(1):235–249.Crossref, Google Scholar
• [54] Vondrák J (2010) Submodularity and curvature: The optimal algorithm. RIMS Kôkyûroku Bessatsu B23:253–266.Google Scholar