Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

The Lovasz θ function, SVMs and finding large dense subgraphs

The Lovasz θ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing θ involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz θ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM−θ graphs, on which the Lovasz θ function can be approximated well by a one-class SVM. This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique of size Θ(n√) in a random graph G(n,12). A classic approach for this problem involves computing the θ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of SVM−θ graph, and as a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. Further, we introduce the notion of a ''common orthogonal labeling'' which extends the notion of a ''orthogonal labelling of a single graph (used in defining the θ function) to multiple graphs. The problem of finding the optimal common orthogonal labelling is cast as a Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs. The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.

Simultaneous feature selection and clustering using particle swarm optimization

Data clustering groups data so that data which are similar to each other are in the same group and data which are dissimilar to each other are in different groups. Since generally clustering is a subjective activity, it is possible to get different clusterings of the same data depending on the need. This paper attempts to find the best clustering of the data by first carrying out feature selection and using only the selected features, for clustering. A PSO (Particle Swarm Optimization)has been used for clustering but feature selection has also been carried out simultaneously. The performance of the above proposed algorithm is evaluated on some benchmark data sets. The experimental results shows the proposed methodology outperforms the previous approaches such as basic PSO and Kmeans for the clustering problem.

Cooperative Particle Swarm Optimization Based Receiver for Large-Dimension MIMO-ZPSC Systems

In this paper, we propose a cooperative particle swarm optimization (CPSO) based channel estimation/equalization scheme for multiple-input multiple-output zero-padded single-carrier (MIMO-ZPSC) systems with large dimensions in frequency selective channels. We estimate the channel state information at the receiver in time domain using a PSO based algorithm during training phase. Using the estimated channel, we perform information symbol detection in the frequency domain using FFT based processing. For this detection, we use a low complexity OLA (OverLap Add) likelihood ascent search equalizer which uses minimum mean square (MMSE) equalizer solution as the initial solution. Multiple iterations between channel estimation and data detection are carried out which significantly improves the mean square error and bit error rate performance of the receiver.

Role of melt convection on optimization of PCM-based heat sink under cyclic heat load

In this article, we study the thermal performance of phase-change material (PCM)-based heat sinks under cyclic heat load and subjected to melt convection. Plate fin type heat sinks made of aluminum and filled with PCM are considered in this study. The heat sink is heated from the bottom. For a prescribed value of heat flux, design of such a heat sink can be optimized with respect to its geometry, with the objective of minimizing the temperature rise during heating and ensuring complete solidification of PCM at the end of the cooling period for a given cycle. For given length and base plate thickness of a heat sink, a genetic algorithm (GA)-based optimization is carried out with respect to geometrical variables such as fin thickness, fin height, and the number of fins. The thermal performance of the heat sink for a given set of parameters is evaluated using an enthalpy-based heat transfer model, which provides the necessary data for the optimization algorithm. The effect of melt convection is studied by taking two cases, one without melt convection (conduction regime) and the other with convection. The results show that melt convection alters the results of geometrical optimization.