We consider judgment aggregation over multiple independent issues, where the chairperson has her own opinion, and can try to bias the outcome by bundling several issues together. Since for each bundle judges must give a uniform answer on all issues, different partitions of the issues may result in an outcome that significantly differs from the "true," issue-wise, decision. We prove that the bundling problem faced by the chairperson, i.e. trying to bias the outcome towards her own opinion, is computationally difficult in the worst case. Then we study the probability that an effective bundling attack exists as the disparity between the opinions of the judges and the chair varies. We show that if every judge initially agrees with the chair on every issue with probability of at least 1/2, then there is almost always a bundling attack (i.e. a partition) where the opinion of the chair on all issues is approved. Moreover, such a partition can be found efficiently. In contrast, when the probability is lower than 1/2 then the chair cannot force her opinion using bundling even on a single issue.

This paper presents a unified framework for intra-view and inter-view constraint propagation on multi-view data. Pairwise constraint propagation has been studied extensively, where each pairwise constraint is defined over a pair of data points from a single view. In contrast, very little attention has been paid to inter-view constraint propagation, which is more challenging since each pairwise constraint is now defined over a pair of data points from different views. Although both intra-view and inter-view constraint propagation are crucial for multi-view tasks, most previous methods can not handle them simultaneously. To address this challenging issue, we propose to decompose these two types of constraint propagation into semi-supervised learning subproblems so that they can be uniformly solved based on the traditional label propagation techniques. To further integrate them into a unified framework, we utilize the results of intra-view constraint propagation to adjust the similarity matrix of each view and then perform inter-view constraint propagation with the adjusted similarity matrices. The experimental results in cross-view retrieval have shown the superior performance of our unified constraint propagation.

Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the Boolean satisfiablity (SAT) problem. One of the most famous SLS algorithms for SAT is WalkSAT, which is an initial algorithm that has wide influence among modern SLS algorithms. Recently, there has been increasing interest in WalkSAT, due to the discovery of its great power on large random 3-SAT instances. However, the performance of WalkSAT on random $k$-SAT instances with $k>3$ lags far behind. Indeed, there have been few works in improving SLS algorithms for such instances. This work takes a large step towards this direction. We propose a novel concept namely $multilevel$ $make$. Based on this concept, we design a scoring function called $linear$ $make$, which is utilized to break ties in WalkSAT, leading to a new algorithm called WalkSAT$lm$. Our experimental results on random 5-SAT and 7-SAT instances show that WalkSAT$lm$ improves WalkSAT by orders of magnitudes. Moreover, WalkSAT$lm$ significantly outperforms state-of-the-art SLS solvers on random 5-SAT instances, while competes well on random 7-SAT ones. Additionally, WalkSAT$lm$ performs very well on random instances from SAT Challenge 2012, indicating its robustness.

A challenging problem in machine learning, information retrieval and computer vision research is how to recover a low-rank representation of the given data in the presence of outliers and missing entries. The L1-norm low-rank matrix factorization (LRMF) has been a popular approach to solving this problem. However, L1-norm LRMF is difficult to achieve due to its non-convexity and non-smoothness, and existing methods are often inefficient and fail to converge to a desired solution. In this paper we propose a novel cyclic weighted median (CWM) method, which is intrinsically a coordinate decent algorithm, for L1-norm LRMF. The CWM method minimizes the objective by solving a sequence of scalar minimization sub-problems, each of which is convex and can be easily solved by the weighted median filter. The extensive experimental results validate that the CWM method outperforms state-of-the-arts in terms of both accuracy and computational efficiency.

We study the stability of cooperative games played over an interaction network, in a model that was introduced by Myerson ['77]. We show that the cost of stability of such games (i.e., the subsidy required to stabilize the game) can be bounded in terms  of natural parameters of their underlying interaction networks. Specifically, we prove that if the treewidth of the interaction network H is k , then the relative cost of stability of any game played over H is at most k + 1, and if the pathwidth of H is k ', then the relative cost of stability is at most k '. We show that these bounds are tight for all k ≥ 2 and all k ' ≥ 1, respectively.

Hierarchical classification (HC) plays an significant role in machine learning and data mining. However, most of the state-of-the-art HC algorithms suffer from high computational costs. To improve the performance of solving, we propose a stochastic perceptron (SP) algorithm in the large margin framework. In particular, a stochastic choice procedure is devised to decide the direction of next iteration. We prove that after finite iterations the SP algorithm yields a sub-optimal solution with high probability if the input instances are separable. For large-scale and high-dimensional data sets, we reform SP to the kernel version (KSP), which dramatically reduces the memory space needed. The KSP algorithm has the merit of low space complexity as well as low time complexity. The experimental results show that our KSP approach achieves almost the same accuracy as the contemporary algorithms on the real-world data sets, but with much less CPU running time.

Transportation Problem is an important aspect which has been widely studied in Operations Research domain. It has been studied to simulate different real life problems. In particular, application of this Problem in NP- Hard Problems has a remarkable significance. In this Paper, we present a comparative study of Transportation Problem through Probabilistic and Fuzzy Uncertainties. Fuzzy Logic is a computational paradigm that generalizes classical two-valued logic for reasoning under uncertainty. In order to achieve this, the notation of membership in a set needs to become a matter of degree. By doing this we accomplish two things viz., (i) ease of describing human knowledge involving vague concepts and (ii) enhanced ability to develop cost-effective solution to real-world problem. The multi-valued nature of Fuzzy Sets allows handling uncertain and vague information. It is a model-less approach and a clever disguise of Probability Theory. We give comparative simulation results of both approaches and discuss the Computational Complexity. To the best of our knowledge, this is the first work on comparative study of Transportation Problem using Probabilistic and Fuzzy Uncertainties.

Fuzzy regression models have been applied to several Operations Research applications viz., forecasting and prediction. Earlier works on fuzzy regression analysis obtain crisp regression coefficients for eliminating the problem of increasing spreads for the estimated fuzzy responses as the magnitude of the independent variable increases. But they cannot deal with the problem of non-uniform spreads. In this work, a three-phase approach is discussed to construct the fuzzy regression model with non-uniform spreads to deal with this problem. The first phase constructs the membership functions of the least-squares estimates of regression coefficients based on extension principle to completely conserve the fuzziness of observations. They are then defuzzified by the centre of area method to obtain crisp regression coefficients in the second phase. Finally, the error terms of the method are determined by setting each estimated spread equal to its corresponding observed spread. The Tagaki-Sugeno inference system is used for improving the accuracy of forecasts. The simulation example demonstrates the strength of fuzzy linear regression model in terms of higher explanatory power and forecasting performance.

In India financial markets have existed for many years. A functionally accented, diverse, efficient and flexible financial system is vital to the national objective of creating a market driven, productive and competitive economy. Today markets of varying maturity exist in equity, debt, commodities and foreign exchange. In this work we attempt to generate prediction rules scheme for stock price movement at Bombay Stock Exchange using an important Soft Computing paradigm viz., Rough Fuzzy Multi Layer Perception. The use of Computational Intelligence Systems such as Neural Networks, Fuzzy Sets, Genetic Algorithms, etc. for Stock Market Predictions has been widely established. The process is to extract knowledge in the form of rules from daily stock movements. These rules can then be used to guide investors. To increase the efficiency of the prediction process, Rough Sets is used to discretize the data. The methodology uses a Genetic Algorithm to obtain a structured network suitable for both classification and rule extraction. The modular concept, based on divide and conquer strategy, provides accelerated training and a compact network suitable for generating a minimum number of rules with high certainty values. The concept of variable mutation operator is introduced for preserving the localized structure of the constituting Knowledge Based sub-networks, while they are integrated and evolved. Rough Set Dependency Rules are generated directly from the real valued attribute table containing Fuzzy membership values. The paradigm is thus used to develop a rule extraction algorithm. The extracted rules are compared with some of the related rule extraction techniques on the basis of some quantitative performance indices. The proposed methodology extracts rules which are less in number, are accurate, have high certainty factor and have low confusion with less computation time.

ETP is NP Hard combinatorial optimization problem. It has received tremendous research attention during the past few years given its wide use in universities. In this Paper, we develop three mathematical models for NSOU, Kolkata, India using FILP technique. To deal with impreciseness and vagueness we model various allocation variables through fuzzy numbers. The solution to the problem is obtained using Fuzzy number ranking method. Each feasible solution has fuzzy number obtained by Fuzzy objective function. The different FILP technique performance are demonstrated by experimental data generated through extensive simulation from NSOU, Kolkata, India in terms of its execution times. The proposed FILP models are compared with commonly used heuristic viz. ILP approach on experimental data which gives an idea about quality of heuristic. The techniques are also compared with different Artificial Intelligence based heuristics for ETP with respect to best and mean cost as well as execution time measures on Carter benchmark datasets to illustrate its effectiveness. FILP takes an appreciable amount of time to generate satisfactory solution in comparison to other heuristics. The formulation thus serves as good benchmark for other heuristics. The experimental study presented here focuses on producing a methodology that generalizes well over spectrum of techniques that generates significant results for one or more datasets. The performance of FILP model is finally compared to the best results cited in literature for Carter benchmarks to assess its potential. The problem can be further reduced by formulating with lesser number of allocation variables it without affecting optimality of solution obtained. FLIP model for ETP can also be adapted to solve other ETP as well as combinatorial optimization problems.