We investigate a family of single-machine scheduling problems that combine convex resource consumption with job rejection, where the performance measure is the total completion time of the accepted jobs. Across four natural variants-distinguished by whether the resource consumption cost and rejection cost appear in the objective or as budget constraints-we analyze their computational complexity and develop efficient algorithms. We show that one variant is polynomially solvable, two variants are weakly NP-hard but admit fully polynomial-time approximation schemes (FPTASs), and the remaining variant admits an FPTAS while its exact complexity remains open.

Abstract Consider a network of k servers and their users. Each server provides a unique service that has a certain utility for each user. Now comes an attacker who wishes to destroy a set of network edges to maximize his net gain, namely the total disconnected utilities of the users minus the total edge‐destruction cost. This k ‐server disconnection problem is N P ‐hard and, furthermore, cannot be approximated within a polynomially computable factor of the optimum when k is part of the input. Even for any fixed k ≥ 2, there is a constant ϵ > 0 such that approximation of the problem within a factor 1/(1 + ϵ) of the optimum is NP‐hard. However, a ( ${1\over 2}+{{1}\over {2^{k+1}-2}}$ )‐approximation can be created in the time of O (2 k ) applications of a min‐cut algorithm. The main idea is to approximate the optimum with special solutions computable in polynomial time due to supermodularity. Therefore, when the the network has, as is usual in most cases, only a few servers, a 0.5‐approximation can be carried out in polynomial time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 273–282 2007