We study the precedence-constrained resource scheduling problem [SICOMP'75]. There are n jobs where each job takes a certain time to finish and has a resource requirement throughout the execution time. There are precedence among the jobs. The problem asks that given a resource budget, schedule the jobs obeying the precedence constraints to minimize makespan (maximum completion time of a job) such that at any point in time, the total resource being used by all the jobs is at most the given resource budget. In the offline setting, an important open question is whether a polynomial-time O(1)-factor approximation algorithm can be found. We prove that hardness of constant factor approximation unless P=NP. In fact, we prove a stronger lower bound that for some constant α > 0, there is no o ((log tmax)α)-factor approximation algorithm for the offline version of the problem with maximum job length tmax, even if there is only one type of resource, unless P = NP.

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs $F$ from a fixed family $\mathcal F$. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs $G$, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [ Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is $\Theta(\log n)$, and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a $47/7\approx6.71$-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs.

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.