Submodular optimization has become increasingly prominent in machine learning, and fairness has drawn much attention. In this paper, we propose to study the fair k-submodular maximization problem and develop a 1/3-approximation greedy algorithm with a running time of O(knB). Our theoretical guarantee matches the best-known k-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a (1/3 ϵ) approximation with ${\mathcal{O}}\left({\frac{{kn}}{\varepsilon }\log \frac{B}{\varepsilon }}\right)$ evaluations of the function−f. Furthermore, for both algorithms, we provide approximation guarantees when the k-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical study and examined the practical implications of fairness. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.

Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form h = f-c, where f is a monotone, non-negative, weakly submodular set function and c is a modular function. We design a deterministic approximation algorithm that runs with O(n/ε log n/(γ ε) ) oracle calls to function h, and outputs a set S such that h(S) ≥ γ(1-ε)f(OPT)-c(OPT)-c(OPT)/γ(1-ε) log f(OPT)/c(OPT), where γ is the submodularity ratio of f. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of f. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function f, and Bayesian A-Optimal design for weakly submodular f. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.

We investigate the problem of multi-objective submodular optimization with cardinality constraint in the context of δ-approximate oracle and show that it is possible to ensure (1 − 1/e)2− 3δ-approximate guarantee for the multi-objective submodular optimization problem. We show that group influence maximization in online social networks is an instance of this optimization problem with cardinality constraint and δ-oracle. We develop a prototype implementation of our solution strategy for group influence maximization problem for networks of different sizes and experimentally justify the effectiveness and scalability of our strategy.

Influence diffusion has been central to the study of the propagation of information in social networks, where influence is typically modeled as a binary property of entities: influenced or not influenced. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. We present an information diffusion model that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study the attitude maximization problem. We prove that the function for computing attitude is monotonic and sub-modular, and the attitude maximization problem is NP-Hard. We present a greedy algorithm for maximization with an approximation guarantee of (1 - 1/e). Using the same model, we also introduce the notion of “actionable” attitude with the aim to study the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. We show that the function for computing actionable attitude, unlike that for computing attitude, is non-submodular but is approximately submodular. We present an approximation algorithm for maximizing actionable attitude in a network. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in the network such as spatial and value distribution of high attitude nodes.

We formulate and study Constrained Influence Maximization problem where a network has two types of nodes-targets and non-targets. Given k and θ, the objective is to find a k-size seed set which maximizes the influence spread among the target nodes and keeps the number of non-targets influenced below the threshold θ. The problem, in general, is NP-hard. We also prove that obtaining a constant factor approximation algorithm for this problem is quasi-NP hard. Nevertheless, we are able to present a greedy algorithm and prove that it has certain approximation guarantees with a multiplicative factor of (1 - 1/e) and an additive error, where the latter is dependent on the underlying network structure. We evaluate the extent of the additive error on several representative social networks of varying sizes, and show that in most scenarios, the greedy algorithm indeed provides a high quality solution efficiently. We also develop a multi-greedy algorithm that attempts to keep multiple seed sets and improves upon the greedy algorithm. However, naive implementations of this algorithm is not practically viable due to prohibitively high time overhead. To address this issue, we develop a two-phase heuristic framework to improve the run times. We have conducted extensive empirical evaluation, which not only validates our algorithms, evaluates their effectiveness and efficiency, but also provides important insights on the interplay between the seed-set size, number of non-targets, the threshold, and the additive approximation error on influence-spread.

In many applications such as service-oriented computing, users often prefer some compositions over the others based on their preferences over non-functional attributes such as security and cost. After a composition is deployed, apart from changes in the functional requirements, service-oriented architectures often have to deal with changes in the user preferences over the non-functional attributes and/or repository of available components. We formulate the problem of adaptation as iterative substitution of appropriate components in a composition, and provide two algorithms that produce a sequence of increasingly preferred adaptations with time: a fast algorithm that searches for preferred adaptations by improving the valuation of the relatively more important attributes, and another that is computationally more intensive but guaranteed to produce at least one preferred adaptation, if one exists.

Choreography analysis has been a crucial problem in service oriented computing. Interactions among services involve message exchanges across organizational boundaries in a distributed computing environment, and in order to build such systems in a reliable manner, it is necessary to develop techniques for analyzing such interactions. Choreography conformance involves verifying that a set of services behave according to a given choreography specification that characterizes their interactions. Unfortunately this is an undecidable problem when services interact with asynchronous communication. In this paper we present techniques that identify if the interaction behavior for a set of services remain the same when asynchronous communication is replaced with synchronous communication. This is called the synchronizability problem and determining the synchronizability of a set of services has been an open problem for several years. We solve this problem in this paper. Our results can be used to identify synchronizable services for which choreography conformance can be checked efficiently. Our results on synchronizability are applicable to any software infrastructure that supports message-based interactions.

We present a goal-directed, local and on-the-fly algorithm for verifying the existence and synthesizing a choreographer forWeb service composition. We use i/o-automata to represent services, the desired functionality of the composition, and a choreographer to achieve the desired service by composing the existing ones. Choreographer existence and synthesis are typically performed by identifying all possible compositions realizable from the existing services and verifying whether one such composition conforms to the desired required functionality. Such a technique is subject to state-space explosion. In light of this, we have developed a tabled-logic programming technique which generates and explores compositions in a goal-directed fashion to prove/disprove the existence of choreographer and to infer whether the desired functionality is realizable. We present a prototype implementation and show the practical applicability of our technique using a variety of composition problems with the corresponding computational savings in terms of number of states and transitions explored.