Basic variable neighborhood search for the minimum sitting arrangement problem The minimum sitting arrangement (MinSA) problem is a linear layout problem consisting in minimizing the number of errors produced when a signed graph is embedded into a line. This problem has been previously tackled by theoretical and heuristic approaches in the literature. In this paper we present a basic variable neighborhood search (BVNS) algorithm for solving the problem. First, we introduce a novel constructive scheme based on the identification of cliques from the input graph, when only the positive edges are considered. The solutions obtained by the constructive procedure are then used as a starting point for the proposed BVNS algorithm. Efficient implementations of the several configurations of the local search procedure within the BVNS are described. The algorithmic proposal is then compared with previous approaches in the state of the art for the MinSA over different sets of referred instances. The obtained results supported by nonparametric statistical tests, indicate that BVNS can be considered as the new stateoftheart algorithm for the MinSA.

A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix In this paper, we consider the problem on minimizing sums of the largest eigenvalues of a symmetric matrix which depends on the decision variable affinely. An important application of this problem is the graph partitioning problem, which arises in layout of circuit boards, computer logic partitioning, and paging of computer programs. Given xe2x88x88xe2x89xa50, we first derive an optimality condition which ensures that the objective function is within xe2x88x88 error bound of the solution. This condition may be used as a practical stopping criterion for any algorithm solving the underlying problem. We also show that, in a neighborhood of the minimizer, the optimization problem can be equivalently formulated as a smooth constrained problem. An existing algorithm on minimizing the largest eigenvalue of a symmetric matrix is shown to be applicable here. This algoritm enjoys the property that if started close enough to the minimizer, then it will converge quadratically. To implement a practical algorithm, one needs to incorporate some technique to generate a good starting point. Since the problem is convex, this can be done by using an algorithm for general convex optimization problems (e.g., Kelleyu0027s cutting plane method or ellipsoid methods), or an algorithm specific for the optimization problem under consideration (e.g., the algorithm developed by Cullum, Donath, and Wolfe). Such union ensures that the overall algorithm has global convergence with quadratic rate. Finally, the results presented in this paper are readily extended on minimizing sums of the largest eigenvalues of a Hermitian matrix.