A note on the quadratic assignment problem

The quadratic assignment problem （QAP） is one of the most interesting and challenging combinatorial optimization problems in existence and one of the most difficult problems in the NP-hard class. Many real-life problems in several areas such as facilities location parallel and distributed computing, combinatorial data analysis and combinatorial optimization problems which have many application in computer engineering and industry can be formulated as a QAP. In this paper, the author give a short note on the QAP, giving our rounding approach with the survey of other algorithms that used to solve this important problem.     

A note on the model reduction problem

A mixed method of model reduction is proposed; it is based on the differentiation method suggested by Gutman et al. [1] and on the usual Padé method. More precisely, the differentiation procedure is used to obtain the reduced-order denominator, thus ensuring stability preservation, while the numerator is obtained by matching the first MacLaurin expansion coefficients of the original system and model transfer functions. The method is computationally very simple and may lead to satisfactory results, as shown by an example where the original system transfer function is taken from the relevant literature.     

A note on the optimal inverter problem

A proof is given that the optimal inverter problem is NP-complete. Other related problems are also shown to be NP-complete.     

A note on the single genotype resolution problem

This note settles the complexity of the single genotype resolution problem showing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R. Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardness of Maximum Resolution problem.     

A note on the terminal Steiner tree problem

In 2002, Lin and Xue [Inform. Process. Lett. 84 (2002) 103-107] introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They presented a ρ+2 approximation algorithm, where ρ is the approximation ratio of the best known efficient algorithm for the regular graph Steiner tree problem. In this note, we derive a simplified algorithm with an improved approximation ratio of 2ρ (currently ρ≈1.550, see [SODA 2000, 2000, pp. 770-790]).     

A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].     

A note on a robust stability problem

A fourth order linear time-invariant system with one uncertain parameter that has been analysed by many authors for robust stability is observed to have an acyclic system matrix. This leads to a simple derivation of a non-conservative robust stability condition, using the Liapunov function that is associated to the acyclic matrix. Some remarks on the time-varying case are also made.     

A note on the truck and trailer routing problem

This study considers the relaxed truck and trailer routing problem (RTTRP), a relaxation of the truck and trailer routing problem (TTRP). TTRP is a variant of the well studied vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service a set of customers with known demands. Some customers may be serviced by a truck pulling a trailer, while the others may only be serviced by a single truck. This is the main difference between TTRP and VRP. The number of available trucks and available trailers is limited in the original TTRP but there are no fixed costs associated with the use of trucks or trailers. Therefore, it is reasonable to relax this fleet size constraint to see if it is possible to further reduce the total routing cost (distance). In addition, the resulting RTTRP can also be used to determine a better fleet mix. We developed a simulated annealing heuristic for solving RTTRP and tested it on 21 existing TTRP benchmark problems and 36 newly generated TTRP instances. Computational results indicate that the solutions for RTTRP are generally better than the best solutions in the literature for TTRP. The proposed SA heuristic is able to find better solutions to 18 of the 21 existing benchmark TTRP instances. The solutions for the remaining three problems are tied with the best so far solutions in the literature. For the 36 newly generated problems, the average percentage improvement of RTTRP solutions over TTRP solutions is about 5%. Considering the ever rising crude oil price, even small reduction in the route length is significant.     

A note on the inclusion problem for szilard languages †

It is shown that the problem of labeling the productions of two regular grammars G ₁ and G ₂ in such a way that the Szilard language of G ₁ is included in the Szilard language of G ₂ is NP-complete.     

A note on classes of complements and the LBA problem

Summary The complements of an AFL form an AFL if and only if is closed under length-preserving universal quantification. The complements of the context-sensitive languages form a principal AFL with a hardest set L ₁. The context-sensitive languages are closed under complementation if and only if L ₁ is context-sensitive.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and DCR74-15091     

A note on the disturbance decoupling problem for retarded systems

The disturbance decoupling problem for linear control systems is to design a feedback control law in such a way that the disturbances do not influence these outputs which are to be regulated. In this note we present a very simple solution to this problem for a rather general class of retarded functional differential equations with delays in the state variables.     

A note on the complexity of the concurrent open shop problem

The concurrent open shop problem is a relaxation of the well known open job shop problem, where the components of a job can be processed in parallel by dedicated, component specific machines. Recently, the problem has attracted the attention of a number of researchers. In particular, Leung et al. (2005) show, contrary to the assertion in Wagneur and Sriskandarajah (1993), that the problem of minimizing the average job completion time is not necessarily strongly NP-hard. Their finding has thus once again opened up the question of the problem's complexity. This paper re-establishes that, even for two machines, the problem is NP-hard in the strong sense.