The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.     

Is Submodularity Testable?

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f:{0,1} ⁿ →?. The distance to submodularity is the minimum fraction of values of f that need to be modified to make f submodular. If this distance is more than ?>0, then we say that f is ?-far from being submodular. The aim is to have an efficient procedure that, given input f that is ?-far from being submodular, certifies that f is not submodular. We analyze a natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be efficient in terms of ?. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.     

Maximizing a deep submodular function optimization with a weighted MAX-SAT problem for trajectory clustering and motion segmentation

Computer vision models are commonly defined for maximum constrained submodular functions lies at the core of low-level and high-level models. In such that, the pixels that are to be grouped or segmenting moving object remains a challenging task. This paper proposes a joint framework for maximizing submodular energy subject to a matroid constraint using Deep Submodular Function (DSF) optimization approximately to solve the weighted MAX-SAT (Maximum Satisfiability) problem and a new trajectory clustering method called Simple Slice Linear clustering (SSLIC) and motion cue method for trajectory clustering and motion segmentation. In this objective function, the illustrative trajectories of a small number are selected automatically by deep submodular maximization. Although, the exploitation of monotone and submodular properties are further maximized and the complexity is reduced by a continuous greedy algorithm. The bound guarantees a fully sliced curve of (1- S/e) to (1–1/e) with less running time. Lastly, the motion is segmented by the motion cue method to accurately differentiate the set of frames for different scenes. Experiments on the Hopkins 155, Berkley Motion Segmentation (BMS) and FBMS-59 datasets display the trajectory clustering and motion segmentation result over its superior performance with respect to 14 quality evaluation metrics. Hence the simulation result shows that the proposed joint framework attains better performance than existing methods on trajectory clustering and motion segmentation task.

     

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

Submodular function minimization is a polynomially solvable combinatorial problem. Unfortunately the best known general-purpose algorithms have high-order polynomial time complexity. In many applications the objective function is locally defined in that it is the sum of cost functions (also known as soft or valued constraints) whose arities are bounded by a constant. We prove that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Such an equivalent instance is the result of establishing optimal soft arc consistency and can hence be found by solving a linear program. From a practical point of view, this provides us with an alternative algorithm for minimizing locally defined submodular functions. From a theoretical point of view, this brings to light a previously unknown connection between submodularity and soft arc consistency.     

Non-dominated sorting genetic algorithm using fuzzy membership chromosome for categorical data clustering

In this research, a data clustering algorithm named as non-dominated sorting genetic algorithm-fuzzy membership chromosome (NSGA-FMC) based on K-modes method which combines fuzzy genetic algorithm and multi-objective optimization was proposed to improve the clustering quality on categorical data. The proposed method uses fuzzy membership value as chromosome. In addition, due to this innovative chromosome setting, a more efficient solution selection technique which selects a solution from non-dominated Pareto front based on the largest fuzzy membership is integrated in the proposed algorithm. The multiple objective functions: fuzzy compactness within a cluster (π) and separation among clusters (sep) are used to optimize the clustering quality. A series of experiments by using three UCI categorical datasets were conducted to compare the clustering results of the proposed NSGA-FMC with two existing methods: genetic algorithm fuzzy K-modes (GA-FKM) and multi-objective genetic algorithm-based fuzzy clustering of categorical attributes (MOGA (π, sep)). Adjusted Rand index (ARI), π, sep, and computation time were used as performance indexes for comparison. The experimental result showed that the proposed method can obtain better clustering quality in terms of ARI, π, and sep simultaneously with shorter computation time.     

A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et?al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.     

An effective suggestion method for keyword search of databases

This paper solves the problem of providing high-quality suggestions for user keyword queries over databases. With the assumption that the returned suggestions are independent, existing query suggestion methods over databases score candidate suggestions individually and return the top-k best of them. However, the top-k suggestions have high redundancy with respect to the topics. To provide informative suggestions, the returned k suggestions are expected to be diverse, i.e., maximizing the relevance to the user query and the diversity with respect to topics that the user might be interested in simultaneously. In this paper, an objective function considering both factors is defined for evaluating a suggestion set. We show that maximizing the objective function is a submodular function maximization problem subject to n matroid constraints, which is an NP-hard problem. An greedy approximate algorithm with an approximation ratio O(\(\frac {1}{1+n}\)) is also proposed. Experimental results show that our suggestion outperforms other methods on providing relevant and diverse suggestions.     

Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems

The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V ₁,V ₂,…,V _k so that $\sum_{i=1}^{k}f(V_{i})$ is minimized where f is a non-negative submodular function on V. In this paper, we design an approximation algorithm for the problem with fixed k. We also analyze the approximation factor of our algorithm for the hypergraph k-cut problem, which is a problem contained by the submodular system k-partition problem.     

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover, with Δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.     

Improving surrogate-assisted variable fidelity multi-objective optimization using a clustering algorithm

Surrogate-assisted evolutionary optimization has proved to be effective in reducing optimization time, as surrogates, or meta-models can approximate expensive fitness functions in the optimization run. While this is a successful strategy to improve optimization efficiency, challenges arise when constructing surrogate models in higher dimensional function space, where the trade space between multiple conflicting objectives is increasingly complex. This complexity makes it difficult to ensure the accuracy of the surrogates. In this article, a new surrogate management strategy is presented to address this problem. A k-means clustering algorithm is employed to partition model data into local surrogate models. The variable fidelity optimization scheme proposed in the author's previous work is revised to incorporate this clustering algorithm for surrogate model construction. The applicability of the proposed algorithm is illustrated on six standard test problems. The presented algorithm is also examined in a three-objective stiffened panel optimization design problem to show its superiority in surrogate-assisted multi-objective optimization in higher dimensional objective function space. Performance metrics show that the proposed surrogate handling strategy clearly outperforms the single surrogate strategy as the surrogate size increases.     

PASS Approximation: A Framework for Analyzing and Designing Heuristics

We introduce a new framework for designing and analyzing algorithms. Our framework applies best to problems that are inapproximable according to the standard worst-case analysis. We circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. Given our parameterized approximation, called PArametrized by the Signature of the Solution (PASS) approximation, we design algorithms with optimal approximation ratios for problems with additive and submodular objective functions such as the capacitated maximum facility location problems. We consider two types of algorithms for these problems. For greedy algorithms, our framework provides a justification for preferring a certain natural greedy rule over some alternative greedy rules that have been used in similar contexts. For LP-based algorithms, we show that the natural LP relaxation for these problems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework. In passing, we note that our results strictly improve over previous results of Kleinberg et al. (J. ACM 51(2):263–280, 2004) concerning the approximation ratio of the greedy algorithm.     

An Algorithm for Clustering Using L1‐Norm Based on Hyperbolic Smoothing Technique

Cluster analysis deals with the problem of organization of a collection of objects into clusters based on a similarity measure, which can be defined using various distance functions. The use of different similarity measures allows one to find different cluster structures in a data set. In this article, an algorithm is developed to solve clustering problems where the similarity measure is defined using the L₁‐norm. The algorithm is designed using the nonsmooth optimization approach to the clustering problem. Smoothing techniques are applied to smooth both the clustering function and the L₁‐norm. The algorithm computes clusters sequentially and finds global or near global solutions to the clustering problem. Results of numerical experiments using 12 real‐world data sets are reported, and the proposed algorithm is compared with two other clustering algorithms.     

A survey of kernel and spectral methods for clustering

Clustering algorithms are a useful tool to explore data structures and have been employed in many disciplines. The focus of this paper is the partitioning clustering problem with a special interest in two recent approaches: kernel and spectral methods. The aim of this paper is to present a survey of kernel and spectral clustering methods, two approaches able to produce nonlinear separating hypersurfaces between clusters. The presented kernel clustering methods are the kernel version of many classical clustering algorithms, e.g., K-means, SOM and neural gas. Spectral clustering arise from concepts in spectral graph theory and the clustering problem is configured as a graph cut problem where an appropriate objective function has to be optimized. An explicit proof of the fact that these two paradigms have the same objective is reported since it has been proven that these two seemingly different approaches have the same mathematical foundation. Besides, fuzzy kernel clustering methods are presented as extensions of kernel K-means clustering algorithm.     

Weighted graph cuts without eigenvectors a multilevel approach

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods--in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast, high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods, such as Metis, have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis and gene network analysis.     

Decision-making based on approximate and smoothed Pareto curves

We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision maker’s approach in which both criteria are combined into a single (usually nonlinear) objective function. Previous work by Papadimitriou and Yannakakis showed how to efficiently approximate the Pareto curve for problems like Shortest Path, Spanning Tree, and Perfect Matching. We wish to determine for which classes of combined objective functions the approximate Pareto curve also yields an approximate solution to the decision maker’s problem. We show that an FPTAS for the Pareto curve also gives an FPTAS for the decision-maker’s problem if the combined objective function is growth bounded like a quasi-polynomial function. If the objective function, however, shows exponential growth then the decision-maker’s problem is NP-hard to approximate within any polynomial factor. In order to bypass these limitations of approximate decision making, we turn our attention to Pareto curves in the probabilistic framework of smoothed analysis. We show that in a smoothed model, we can efficiently generate the (complete and exact) Pareto curve with a small failure probability if there exists an algorithm for generating the Pareto curve whose worst-case running time is pseudopolynomial. This way, we can solve the decision-maker’s problem w.r.t. any non-decreasing objective function for randomly perturbed instances of, e.g. Shortest Path, Spanning Tree, and Perfect Matching.     

Double indices-induced FCM clustering and its integration with fuzzy subspace clustering

As one of the most popular algorithms for cluster analysis, fuzzy c-means (FCM) and its variants have been widely studied. In this paper, a novel generalized version called double indices-induced FCM (DI-FCM) is developed from another perspective. DI-FCM introduces a power exponent r into the constraints of the objective function such that the fuzziness index m is generalized and a new criterion of selecting an appropriate fuzziness index m is defined. Furthermore, it can be explained from the viewpoint of entropy concept that the power exponent r facilitates the introduction of entropy-based constraints into fuzzy clustering algorithms. As an attractive and judicious application, DI-FCM is integrated with a fuzzy subspace clustering (FSC) algorithm so that a new fuzzy subspace clustering algorithm called double indices-induced fuzzy subspace clustering (DI-FSC) algorithm is proposed for high-dimensional data. DI-FSC replaces the commonly used Euclidean distance with the feature-weighted distance, resulting in having two fuzzy matrices in the objective function. A convergence proof of DI-FSC is also established by applying Zangwill’s convergence theorem. Several experiments on both artificial data and real data were conducted and the experimental results show the effectiveness of the proposed algorithm.     

A design and analysis of objective function-based unsupervised neural networks for fuzzy clustering

Fuzzy clustering has played an important role in solving many problems. In this paper, we design an unsupervised neural network model based on a fuzzy objective function, called OFUNN. The learning rule for the OFUNN model is a result of the formal derivation by the gradient descent method of a fuzzy objective function. The performance of the cluster analysis algorithm is often evaluated by counting the number of crisp clustering errors. However, the number of clustering errors alone is not a reliable and consistent measure for the performance of clustering, especially in the case of input data with fuzzy boundaries. We introduce two measures to evaluate the performance of the fuzzy clustering algorithm. The clustering results on three data sets, Iris data and two artificial data sets, are analyzed using the proposed measures. They show that OFUNN is very competitive in terms of speed and accuracy compared to the fuzzy c-means algorithm.     

Soft arc consistency revisited

The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations Research, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search.In this paper, we extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal arc consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC).To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft arc consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions.These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.     

Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning

Spatial crowdsourcing has emerged as a new paradigm for solving problems in the physical world with the help of human workers. A major challenge in spatial crowdsourcing is to assign reliable workers to nearby tasks. The goal of such task assignment process is to maximize the task completion in the face of uncertainty. This process is further complicated when tasks arrivals are dynamic and worker reliability is unknown. Recent research proposals have tried to address the challenge of dynamic task assignment. Yet the majority of the proposals do not consider the dynamism of tasks and workers. They also make the unrealistic assumptions of known deterministic or probabilistic workers’ reliabilities. In this paper, we propose a novel approach for dynamic task assignment in spatial crowdsourcing. The proposed approach combines bi-objective optimization with combinatorial multi-armed bandits. We formulate an online optimization problem to maximize task reliability and minimize travel costs in spatial crowdsourcing. We propose the distance-reliability ratio (DRR) algorithm based on a combinatorial fractional programming approach. The DRR algorithm reduces travel costs by 80% while maximizing reliability when compared to existing algorithms. We extend the DRR algorithm for the scenario when worker reliabilities are unknown. We propose a novel algorithm (DRR-UCB) that uses an interval estimation heuristic to approximate worker reliabilities. Experimental results demonstrate that the DRR-UCB achieves high reliability in the face of uncertainty. The proposed approach is particularly suited for real-life dynamic spatial crowdsourcing scenarios. This approach is generalizable to the similar problems in other areas in expert systems. First, it encompasses online assignment problems when the objective function is a ratio of two linear functions. Second, it considers situations when intelligent and repeated assignment decisions are needed under uncertainty.