Hardness of Vertex Deletion and Project Scheduling

by Ola Svensson

Theory of Computing, Volume 9(24), pp. 759-781, 2013

Bibliography with links to cited articles

[1]   Nikhil Bansal and Subhash Khot: Optimal long code test with one free bit. In Proc. 50th FOCS, pp. 453–462. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.23]

[2]   Nikhil Bansal and Subhash Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]

[3]   Prabuddha De, E. James Dunne, Jay B. Ghosh, and Charles E. Wells: The discrete time-cost tradeoff problem revisited. European Journal of Operational Research, 81(2):225–238, 1995. [doi:10.1016/0377-2217(94)00187-H]

[4]   Irit Dinur and Shmuel Safra: On the hardness of approximating minimum vertex cover. Ann. of Math., 162(1):439–485, 2005. Preliminary version in STOC’02. See also at ECCC. [doi:10.4007/annals.2005.162.439]

[5]   Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. Preliminary version in IPCO’95. [doi:10.1007/PL00009191]

[6]   Delbert R. Fulkerson: A network flow computation for project cost curves. Management Science, 7(2):167–178, 1961. [doi:10.1287/mnsc.7.2.167]

[7]   Alexander Grigoriev and Gerhard J. Woeginger: Project scheduling with irregular costs: complexity, approximability, and algorithms. Acta Inf., 41(2-3):83–97, 2004. Preliminary version in ISAAC’02. [doi:10.1007/s00236-004-0150-2]

[8]   Venkatesan Guruswami, Johan HÃ¥stad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878–914, 2011. Preliminary versions in FOCS’08 and in CCC’09. See also at ECCC. [doi:10.1137/090756144]

[9]   Richard M. Karp: Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp. 85–103. Springer, 1972. [doi:10.1007/978-1-4684-2001-2_9]

[10]   James E. Kelley, Jr.: Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3):296–320, 1961. [doi:10.1287/opre.9.3.296]

[11]   James E. Kelley, Jr. and Morgan R. Walker: Critical-path planning and scheduling. In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference, pp. 160–173. ACM Press, 1959. [doi:10.1145/1460299.1460318]

[12]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[13]   Frank Thomson Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. Preliminary version in FOCS’88. [doi:10.1145/331524.331526]

[14]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: Invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[15]   Doowon Paik, Sudhakar M. Reddy, and Sartaj Sahni: Deleting vertices to bound path length. IEEE Trans. Computers, 43(9):1091–1096, 1994. [doi:10.1109/12.312117]

[16]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

[17]   Paul D. Seymour: Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. [doi:10.1007/BF01200760]

[18]   Martin Skutella: Approximation algorithms for the discrete time-cost tradeoff problem. Math. Oper. Res., 23(4):909–929, 1998. Preliminary version in SODA’97. [doi:10.1287/moor.23.4.909]

[19]   Ola Svensson: Hardness of vertex deletion and project scheduling. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), pp. 301–312. Springer, 2012. [doi:10.1007/978-3-642-32512-0_26]