A population-based iterated greedy algorithm for the minimum weight vertex cover problem

Given an undirected, vertex-weighted graph, the goal of the minimum weight vertex cover problem is to find a subset of the vertices of the graph such that the subset is a vertex cover and the sum of the weights of its vertices is minimal. This problem is known to be NP-hard and no efficient algorithm is known to solve it to optimality. Therefore, most existing techniques are based on heuristics for providing approximate solutions in a reasonable computation time.Population-based search approaches have shown to be effective for solving a multitude of combinatorial optimization problems. Their advantage can be identified as their ability to find areas of the space containing high quality solutions. This paper proposes a simple and efficient population-based iterated greedy algorithm for tackling the minimum weight vertex cover problem. At each iteration, a population of solutions is established and refined using a fast randomized iterated greedy heuristic based on successive phases of destruction and reconstruction. An extensive experimental evaluation on a commonly used set of benchmark instances shows that our algorithm outperforms current state-of-the-art approaches.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

Determining the interior point of a system of linear inequalities

A convergence result is proved for the dual variables of a completely degenerate linear programming problem. The successive approximations are shown to converge to an interior point of the dual solution set.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 67–74, January–February, 1992.     

Constructing a committee of a system of linear inequalities

A representation of an arbitrary system of strict linear inequalities in R ⁿ as a system of points is proposed. The representation is obtained by using a so-called polarity. Based on this representation an algorithm for constructing a committee of a plane system of linear inequalities is given. A solution of two problems on minimal committee of a plane system is proposed. The obtained solutions to these problems can be found by means of the proposed algorithm. Kobylkin K.S. Born in 1977. Graduated from Ural State University in 2000. At the present time Kobylkin K.S. works at Institute of Mathematics and Mechanics of the Ural Division of the Russian Academy of Sciences. Scientific interests: pattern recognition, mathematical economics. Author of four publications. Member of the Russian Association for Pattern Recognition and Image Analysis and IAPR.     

Solvability conditions for a second-order system of linear matrix inequalities

The necessary and sufficient conditions for solvability of a second-order system of linear matrix inequalities that can be reduced to two or three scalar inequalities of the second order are presented.     

Hybrid system stability and robustness verification using linear matrix inequalities

This paper addresses issues concerning exponential stability and robustness of hybrid systems. Stability conditions using Lyapunov techniques are given. The search for the Lyapunov functions is formulated as a linear matrix inequality (LMI) problem for hybrid systems with affine as well as non-linear vector fields. It is shown how the Lyapunov approach most advantageously also can be used to guarantee stability despite the presence of model uncertainties. Several examples are given to illustrate the theory.     

Design method for a new control system for an autonomous underwater vehicle using linear matrix inequalities

The independent administrative corporation Japan Agency for Marine–Earth Science and Technology (JAMSTEC) has developed a small light autonomous underwater vehicle (AUV) named marine robot experimental 1 (MR-X1).¹ The motion control of MR-X1 is considered in this article. Since the dynamics of MR-X1 mainly depends on its own speed, the motion control is a nonlinear control system. We propose a new controller design method for this system using linear matrix inequalities (LMIs). This algorithm gives a solution as a linear matrix inequality, and can be adapted to solve many LMIs simultaneously. LMIs can be obtained by substituting several speeds into the dynamics of the MR-X1. The proposed controller, which can be derived from the solution of the LMIs, was adapted to MR-X1 and showed good performance in experiments. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

Distributed solver for linear matrix inequalities:an optimization perspective

In this paper,we develop a distributed solver for a group of strict(non-strict)linear matrix inequalities over a multi-agent network,where each agent only knows...     

Distributed solver for linear matrix inequalities: an optimization perspective

In this paper, we develop a distributed solver for a group of strict (non-strict) linear matrix inequalities over a multi-agent network, where each agent only knows one inequality, and all agents co-operate to reach a consensus solution in the intersection of all the feasible regions. The formulation is transformed into a distributed optimization problem by introducing slack variables and consensus constraints. Then, by the primal–dual methods, a distributed algorithm is proposed with the help of projection operators and derivative feedback. Finally, the convergence of the algorithm is analyzed, followed by illustrative simulations.     

On separating cover inequalities for the multidimensional knapsack problem

We propose a simple and a quite efficient separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs is usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of our experiments with a small set of randomly generated problems and problems taken from the literature indicate that the method may be a reasonable alternative to the one currently in use.     

A parallel algorithm for approximating the minimum cycle cover

We address the problem of approximating aminimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to aminimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of 0(1 +n logn/(m + n) of the minimum-sized cover usingO(log² n) time on (m + n)/logn processors.Research supported by ONR Grant N00014-88-K-0243 and DARPA Grant N00039-88-C0113 at Harvard University.Research supported by a graduate fellowship from GE. Additional support provided by Air Force Contract AFOSR-86-0078, and by an NSF PYI awarded to David Shmoys, with matching funds from IBM, Sun Microsystems, and UPS.     

Finding the longest common nonsuperstring in linear time

String inclusion and non-inclusion problems have been vigorously studied in such diverse fields as molecular biology, data compression, and computer security. Among the well-known string inclusion or non-inclusion notions, we are interested in the longest common nonsuperstring. Given a set of strings, the longest common nonsuperstring problem is finding the longest string that is not a superstring of any string in the given set. It is known that the longest common nonsuperstring problem is solvable in polynomial time.In this paper, we propose an efficient algorithm for the longest common nonsuperstring problem. The running time of our algorithm is linear with respect to the sum of the lengths of the strings in the given set, using generalized suffix trees.     

Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

New results for the minimum weight triangulation problem

Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set ofn points inO(n ³⁾ time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.This research was done while the second author was with the Department of Computer Science, Virginia Polytechnic Institute and State University.     

基于IIS总线的嵌入式音频系统的设计

本文介绍了基于IIS总线的嵌入式数字音频系统,实现了以Samsung S3C44B0 ARM7处理器为主控核心、以Philips UDA1341TS为编解码芯片的软硬件设计方案。硬件方面,实现了NOR Flash,晶振电路,复位电路,串口电路,JTAG接口电路的设计,并建立了与UDA1341TS的连接;软件方面,UDA1341芯片提供放音和录音接口,可直接驱动耳机或其他音频设备,实现了音频信号的A／D、D／A转换、存储、回放等功能。该系统具有设计灵活、扩展性好和数据处理速度快等优点。