Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover

References

• [1] Alpern S, Lidbetter T (2013) Mining coal or finding terrorists: The expanding search paradigm. Oper. Res. 61(2):265–279.Link, Google Scholar
• [2] Ambühl C, Mastrolilli M (2009) Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4):488–503.Crossref, Google Scholar
• [3] Ambühl C, Mastrolilli 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
• [4] Azar Y, Gamzu I, Yin X (2009) Multiple intents re-ranking. Proc. 41st Annual ACM Sympos. Theory Comput. (ACM, New York), 669–678.Google Scholar
• [5] Bansal N, Khot S (2009) Optimal long code test with one free bit. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 453–462.Google Scholar
• [6] Bansal N, Gupta A, Krishnaswamy R (2010) A constant factor approximation algorithm for generalized min-sum set cover. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1539–1545.Google Scholar
• [7] Bansal N, Batra J, Farhadi M, Tetali P (2021) Improved approximations for min sum vertex cover and generalized min sum set cover. Proc. 2021 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 998–1005.Google Scholar
• [8] Barenholz U, Feige U, Peleg D (2006) Improved approximation for min-sum vertex cover. Technical Report MCS06-07, Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel.Google Scholar
• [9] Bar-Noy A, Bellare M, Halldórsson MM, Shachnai H, Tamir T (1998) On chromatic sums and distributed resource allocation. Inform. Comput. 140(2):183–202.Crossref, Google Scholar
• [10] Charikar M, Naamad Y, Wirth A (2016) On approximating target set selection. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, 4:1–4:16.Google Scholar
• [11] Chekuri C, Motwani R (1999) Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1–2):29–38.Crossref, Google Scholar
• [12] 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
• [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] Correa JR, Schulz AS (2005) Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4):1005–1021.Link, Google Scholar
• [15] Dinur I, Steurer D (2014) Analytical approach to parallel repetition. Proc. 46th Annual ACM Sympos. Theory Comput. (ACM, New York), 624–633.Google Scholar
• [16] Eastman WL, Even S, Isaacs IM (1964) Bounds for the optimal scheduling of n jobs on m processors. Management Sci. 11(2):268–279.Link, Google Scholar
• [17] Erlebach T, Kääb V, Möhring RH (2003) Scheduling AND/OR-networks on identical parallel machines. Internat. Workshop Approximation Online Algorithms, LNCS, vol. 2909 (Springer, Berlin, Heidelberg), 123–136.Google Scholar
• [18] Feige U, Lovász L, Tetali P (2002) Approximating min-sum set cover. Internat. Workshop Approximation Algorithms Combin. Optim., LNCS, vol. 2462 (Springer, Berlin, Heidelberg), 94–107.Google Scholar
• [19] Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219–234.Crossref, Google Scholar
• [20] Fokkink R, Lidbetter T, Végh LA (2019) On submodular search and machine scheduling. Math. Oper. Res. 44(4):1431–1449.Link, Google Scholar
• [21] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (WH Freeman and Company, San Francisco).Google Scholar
• [22] Goemans MX (1996) Cited as personal communication in [49].Google Scholar
• [23] Goemans MX (1997) Improved approximation algorithms for scheduling with release dates. Proc. Eighth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 591–598.Google Scholar
• [24] Goemans MX, Queyranne M, Schulz AS, Skutella M, Wang Y (2002) Single machine scheduling with release dates. SIAM J. Discrete Math. 15(2):165–192.Crossref, Google Scholar
• [25] Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5:287–326.Crossref, Google Scholar
• [26] Grötschel M, Jünger M, Reinelt G (1985) Facets of the linear ordering polytope. Math. Programming 33(1):43–60.Crossref, Google Scholar
• [27] Hall LA, Shmoys DB, Wein J (1996) Scheduling to minimize average completion time: Off-line and on-line algorithms. Proc. Seventh Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 142–151.Google Scholar
• [28] Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3):513–544.Link, Google Scholar
• [29] Happach F (2021) Makespan minimization with OR-precedence constraints. J. Scheduling 24:319–328.Crossref, Google Scholar
• [30] Happach F, Schulz AS (2020) Precedence-constrained scheduling and min-sum set cover. Approximation and Online Algorithms, LNCS, vol. 11926 (Springer, Berlin, Heidelberg), 170–187.Crossref, Google Scholar
• [31] Hassin R, Levin A (2005) An approximation algorithm for the minimum latency set cover problem. Algorithms–ESA 2005, LNCS, vol. 3669 (Springer, Berlin, Heidelberg), 726–733.Crossref, Google Scholar
• [32] Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3):555–556.Crossref, Google Scholar
• [33] Im S, Sviridenko M, van der Zwaan R (2014) Preemptive and non-preemptive generalized min sum set cover. Math. Programming 145(1–2):377–401.Crossref, Google Scholar
• [34] Iwata S, Tetali P, Tripathi P (2012) Approximating minimum linear ordering problems. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, LNCS, vol. 7408 (Springer, Berlin, Heidelberg), 206–217.Crossref, Google Scholar
• [35] Johannes B (2005) On the complexity of scheduling unit-time jobs with OR-precedence constraints. Oper. Res. Lett. 33(6):587–596.Crossref, Google Scholar
• [36] Johnson DS (1974) Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9(3):256–278.Crossref, Google Scholar
• [37] Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Computations (Springer), 85–103.Crossref, Google Scholar
• [38] Khot S (2002) On the power of unique 2-prover 1-round games. Proc. 34th Annual ACM Sympos. Theory Comput. (ACM, New York), 767–775.Google Scholar
• [39] Lawler E (1978) Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2:75–90.Crossref, Google Scholar
• [40] Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper. Res. 26(1):22–35.Link, Google Scholar
• [41] Lovász L (1975) On the ratio of optimal integral and fractional covers. Discrete Math. 13(4):383–390.Crossref, Google Scholar
• [42] 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
• [43] McClintock J, Mestre J, Wirth A (2017) Precedence-constrained min sum set cover. 28th Internat. Sympos. Algorithms Computat., Leibniz International Proceedings in Informatics (LIPIcs) (Schloss Dagstuhl, Germany), vol. 92, 55:1–55:12.Google Scholar
• [44] Munagala K, Babu S, Motwani R, Widom J (2005) The pipelined set cover problem. Internat. Conf. Database Theory, LNCS, vol. 3363 (Springer, Berlin, Heidelberg), 83–98.Google Scholar
• [45] Potts CN (1980) An algorithm for the single machine sequencing problem with precedence constraints. Combinatorial Optimization II, Mathematical Programming Studies, vol. 13, 78–87.Crossref, Google Scholar
• [46] Queyranne M (1993) Structure of a simple scheduling polyhedron. Math. Programming 58(1–3):263–285.Crossref, Google Scholar
• [47] Queyranne M, Schulz AS (1994) Polyhedral approaches to machine scheduling. Technical Report 408/1994, Department of Mathematics, Technical University of Berlin.Google Scholar
• [48] Schulz AS (1996) Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Internat. Conf. Integer Programming Combin. Optim., LNCS, vol. 1084 (Springer, Berlin, Heidelberg), 301–315.Google Scholar
• [49] Schulz AS, Skutella M (1997) Random-based scheduling: New approximations and LP lower bounds. Internat. Workshop Randomization Approximation Techniques Comput. Sci., LNCS, vol. 1269 (Springer, Berlin, Heidelberg), 119–133.Google Scholar
• [50] Sidney JB (1975) Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2):283–298.Link, Google Scholar
• [51] Skutella M, Williamson DP (2011) A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6):433–436.Crossref, Google Scholar
• [52] Smith WE (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1–2):59–66.Crossref, Google Scholar
• [53] Sousa JP, Wolsey LA (1992) A time indexed formulation of non-preemptive single machine scheduling problems. Math. Programming 54(1–3):353–367.Crossref, Google Scholar
• [54] Woeginger GJ (2003) On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1):237–252.Crossref, Google Scholar
• [55] Wolsey LA (1985) Mixed integer programming formulations for production planning and scheduling problems. Invited talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge, MA.Google Scholar