Scheduling within a limited budget is closely related to several much studied scheduling with compression and rescheduling problems, and is also a variant of the more recent model of scheduling with testing. In this problem, one seeks to minimize the makespan for a set of jobs that are to be processed on a number of parallel identical machines. Each job J j is given an upper bound u j on its actual processing time p j , and a testing fee c j . In the offline case, the processing time p j is known to the scheduler; while in the oblivious case, p j is revealed to the scheduler only if the testing fee c j is paid. So the scheduler can choose to execute J j on any one of the machines non-preemptively for u j time or pay for the testing and then execute the job for p j time. The scheduler is given a budget B to pay for testing and seeks to minimize the makespan within that budget. The offline problem is denoted as P ∣ u j , p j , c j , B ∣ C max , and the oblivious problem is denoted as P ∣ u j , − , c j , B ∣ C max , where P stands for multiple parallel identical machines with the number of machines being part of the input. We contribute a polynomial-time approximation scheme (PTAS) for the offline problem P ∣ u j , p j , c j , B ∣ C max , which leads to an almost tight ( 2 + ϵ ) -competitive algorithm for the oblivious problem P ∣ u j , − , c j , B ∣ C max .

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V , E ) such that each path has length at least k , called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1 , but for a general k ≥ 2 , there is no approximation algorithm directly for the problem. We present the first local search ( 0.4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1 , and a 1.4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k=3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers' attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of 3/2, which was recently improved to 13/9 and further to 4/3. We investigate the 3/2-approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for l-paths, l in {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios 13/9 and 4/3. When switching back to the unweighted objective function, we prove the approximation ratio 21/16 via amortized analysis.