A Variable Parameter (VP) analysis, that we introduce here, aims to give a precise algorithm time complexity expression in which an exponent appears solely in terms of a variable parameter. A variable parameter is the number of objects with specific problem-dependent properties. Here we describe two VP-algorithms, an implicit enumeration algorithm and a polynomial-time approximation scheme for a strongly $NP$-hard problem of scheduling $n$ independent jobs with release and due times on one machine to minimize the maximum job lateness. For the problem considered, a variable parameter is the number of a special kind of the so-called ``emerging'' jobs. A partial solution without these jobs is constructed in a low degree polynomial time, and an exponential time procedure (in the number of variable parameters) is carried out to augment it to a complete optimal solution. In the alternative time complexity expressions that we derive, the exponential dependence is solely on some job parameters. Applying the fixed parameter analysis to these estimations, a purely polynomial-time dependence is obtained. Both, the intuitive probabilistic estimation and an extensive experimental study support an intuitively evident conjecture that the total number of the variable parameters is far less than $n$. In particular, its ratio to $n$ asymptotically converges to 0.
In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends on the structure of a given problem instance and tends to have a favorable asymptotic behavior when the size of the input increases. While applying the VPA to an intractable optimization problem with $n$ objects, the exponential-time dependence in enumeration of the feasible solution set is attributed solely to the variable parameter $ν$, $ν<<n$. As opposed to the FPA, the VPA does not imply any restriction on some problem parameters, it rather takes an advantage of a favorable nature of the problem, which permits to reduce the cost of enumeration of the solution space. Our main technical contribution is a variable parameter algorithm for a strongly $\mathsf{NP}$-hard single-machine scheduling problem to minimize maximum job lateness. The target variable parameter $ν$ is the number of jobs with some specific characteristics, the ``emerging'' ones. The solution process is separated in two phases. At phase 1 a partial solution including $n-ν$ non-emerging jobs is constructed in a low degree polynomial time. At phase 2 less than $ν!$ permutations of the $ν$ emerging jobs are considered. Each of them are incorporated into the partial schedule of phase 1. Doe to the results of an earlier conducted experimental study, $ν/n$ varied from $1/4$ for small problem instances to $1/10$ for the largest tested problem instances, so that that the ratio becomes closer to 0 for large $n$s.