Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

Optimal testing and repairing a failed series system

We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error ɛ = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.     

Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration

This article studies a single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity. We assume that after maintenance activity, the machine will revert to its initial condition and the aging effects will start anew. Moreover, due to the restriction of budget of maintenance, the limitation of the maintenance frequency on the machine is assumed to be known in advance. The optional maintenance activity of this study means that the starting time of the maintenance activity is unknown in advance. It can be scheduled immediately after the processing of any job that has been completed. Therefore, the planner must to make decision on whether or when to schedule the maintenance activity during the scheduling horizon to optimal the performance measures. The objective is to minimize the makespan. We first show that the addressed problem is NP-hard in the strong sense. Then a fully polynomial-time approximation scheme (FPTAS) for the proposed problem is presented.     

An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

This paper consider m uniform (parallel) machine scheduling with linear deterioration to minimize the makespan. In an uniform machine environment, all machines have different processing speeds. Linear deterioration means that job’s actual processing time is a linear increasing function on its execution starting time. We propose a fully polynomial-time approximation scheme (FPTAS) to show the problem is NP-hard in the ordinary sense.     

Staying safe and visible via message sharing in online social networks

As an imperative channel for fast information propagation, online social networks (OSNs) also have their defects. One of them is the information leakage, i.e., information could be spread via OSNs to the users whom we are not willing to share with. Thus the problem of constructing a circle of trust to share information with as many friends as possible without further spreading it to unwanted targets has become a challenging research topic but still remained open. Our work is the first attempt to study the Maximum Circle of Trust problem seeking to share the information with the maximum expected number of poster’s friends such that the information spread to the unwanted targets is brought to its knees. First, we consider a special and more practical case with the two-hop information propagation and a single unwanted target. In this case, we show that this problem is NP-hard, which denies the existence of an exact polynomial-time algorithm. We thus propose a Fully Polynomial-Time Approximation Scheme (FPTAS), which can not only adjust any allowable performance error bound but also run in polynomial time with both the input size and allowed error. FPTAS is the best approximation solution one can ever wish for an NP-hard problem. We next consider the number of unwanted targets is bounded and prove that there does not exist an FPTAS in this case. Instead, we design a Polynomial-Time Approximation Scheme (PTAS) in which the allowable error can also be controlled. When the number of unwanted targets are not bounded, we provide a randomized algorithm, along with the analytical theoretical bound and inapproximaibility result. Finally, we consider a general case with many hops information propagation and further show its #P-hardness and propose an effective Iterative Circle of Trust Detection (ICTD) algorithm based on a novel greedy function. An extensive experiment on various real-world OSNs has validated the effectiveness of our proposed approximation and ICTD algorithms. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem

A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/³) and O(n · 1/) space, respectively. Our new approximation scheme requires only O(n + 1/²) space while also reducing the running time.     

A “maximum node clustering” problem

In this note we introduce a graph problem, called Maximum Node Clustering (MNC). We prove that the problem (which is easily shown to be strongly NP-complete) can be approximated in polynomial time within a ratio arbitrarily close to 2. For the special case where the graph is a tree, the problem is NP-complete in the ordinary sense; for this case we present a pseudopolynomial algorithm based on dynamic programming, and a related Fully Polynomial Time Approximation Scheme (FPTAS). Also, the tree case is shown to be exactly solvable in time, where n is the number of nodes.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

Efficient estimation of the accuracy of the maximum likelihood method for ancestral state reconstruction

The marginal maximum likelihood method is a widely-used method for ancestral state reconstruction. Given an evolution model (a phylogeny tree and the edge mutation rates) and the extant states (states on leaves), the method computes efficiently the most likely ancestral state on the root. However, when the extant states are randomly generated by using the evolutionary model, it is unknown how to efficiently calculate the expected reconstruction accuracy of the marginal maximum likelihood method. In this paper, a fully polynomial time approximation scheme (FPTAS) is presented for the calculation.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.     

Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width

We study the problems of non-preemptively scheduling and packing malleable and parallel tasks with precedence constraints to minimize the makespan. In the scheduling variant, we allow the free choice of processors; in packing, each task must be assigned to a contiguous subset. Malleable tasks can be processed on different numbers of processors with varying processing times, while parallel tasks require a fixed number of processors. For precedence constraints of bounded width, we resolve the complexity status of the problem with any number of processors and any width bound. We present an FPTAS based on Dilworth’s decomposition theorem for the NP-hard problem variants, and exact efficient algorithms for all remaining special cases. For our positive results, we do not require the otherwise common monotonous penalty assumption on the processing times of malleable tasks, whereas our hardness results hold even when assuming this restriction. We complement our results by showing that these problems are all strongly NP-hard under precedence constraints which form a tree.     

Flows with unit path capacities and related packing and covering problems

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an O(?m)O(\sqrt{m}) -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.     

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

Minimizing the total cost of barrier coverage in a linear domain

Barrier coverage, as one of the most important applications of wireless sensor network (WSNs), is to provide coverage for the boundary of a target region. We study the barrier coverage problem by using a set of n sensors with adjustable coverage radii deployed along a line interval or circle. Our goal is to determine a range assignment \(\mathbf {R}=({r_{1}},{r_{2}}, \ldots , {r_{n}})\) of sensors such that the line interval or circle is fully covered and its total cost \(C(\mathbf {R})=\sum _{i=1}^n {r_{i}}^\alpha \) is minimized. For the line interval case, we formulate the barrier coverage problem of line-based offsets deployment, and present two approximation algorithms to solve it. One is an approximation algorithm of ratio 4 / 3 runs in \(O(n^{2})\) time, while the other is a fully polynomial time approximation scheme (FPTAS) of computational complexity \(O(\frac{n^{2}}{\epsilon })\). For the circle case, we optimally solve it when \(\alpha = 1\) and present a \(2(\frac{\pi }{2})^\alpha \)-approximation algorithm when \(\alpha > 1\). Besides, we propose an integer linear programming (ILP) to minimize the total cost of the barrier coverage problem such that each point of the line interval is covered by at least k sensors.     

The density maximization problem in graphs

We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G=(V,E) with edge weights w _e ∈? and edge lengths ? _e ∈? for e∈E we define the density of a pattern subgraph H=(V′,E′)?G as the ratio ?(H)=∑ _e∈E′ w _e /∑ _e∈E′ ? _e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard, even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.