Optimizing top-k retrieval： submodularity analysis and search strategies

The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k re- trieval problem in the framework of facility location analysis and prove he submodularity of that objective function which provides a theoretical approximation guarantee of factor 1 -1/ε for the （best-first） greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first ob- tains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.

A Note on Submodularity Preserved Involving the Rank Functions

In many kinds of games with economic significance,it is very important to study the submodularity of functions.In this paper,wemainly study the problem of maximizing a concave function over an intersection of two matroids.We obtain that the submod-ularity may not be preserved,but it involves one maximal submodular problem(or minimal supermodular problem)with some conditions.Moreover,we also present examples showing that these conditions can be satisfied.

临近最优主动学习的藏语语音识别方法研究

语音识别模型需要大量带标注语音语料进行训练,作为少数民族语言的藏语,由于语音标注专家十分匮乏,人工标注语音语料是一件非常费时费力的工作。然而,主动学习方法可以根据语音识别的目标从大量未标注的语音数据中挑选一些具有价值的样本交给用户进行标注,以便利用少量高质量的训练样本构建与大数据量训练方式一样精准的识别模型。研究了基于主动学习的藏语拉萨话语音语料选择方法,提出了一种临近最优的批量样本选择目标函数,并验证了其具有submodular函数性质。通过实验验证,该方法能够使用较少的训练数据保证语音识别模型的精度,从而减少了人工标注语料的工作量。

Influence Maximization for Cascade Model with Diffusion Decay in Social Networks

Maximizing the spread of influence is to select a set of seeds with specified size to maximize the spread of influence under a certain diffusion model in a social network. In the actual spread process, the activated probability of node increases with its newly increasing activated neighbors, which also decreases with time. In this paper, we focus on the problem that selects k seeds based on the cascade model with diffusion decay to maximize the spread of influence in social networks. First, we extend the independent cascade model to incorporate the diffusion decay factor, called as the cascade model with diffusion decay and abbreviated as CMDD. Then, we discuss the objective function of maximizing the spread of influence under the CMDD, which is NP-hard. We further prove the monotonicity and submodularity of this objective function. Finally, we use the greedy algorithm to approximate the optimal result with the ration of 1 ? 1/e.

Selecting Seeds for Competitive Influence Spread Maximization in Social Networks

There exist two or more competing products in viral marketing, and the companies can exploit the social interactions of users to propagate the awareness of products. In this paper, we focus on selecting seeds for maximizing the competitive influence spread in social networks. First, we establish the possible graphs based on the propagation probability of edges, and then we use the competitive influence spread model (CISM) to model the competitive spread under the possible graph. Further, we consider the objective function of selecting k seeds of one product under the CISM when the seeds of another product have been known, which is monotone and submodular, and thus we use the CELF (cost-effective lazy forward) algorithm to accelerate the greedy algorithm that can approximate the optimal with 1 ? 1/e. Experimental results verify the feasibility and effectiveness of our method.

Equivalence between Linear Tangle and Maximal Single Ideal

The concept of linear tangle was introduced as an obstruction to mixed searching number. The concept of (maximal) single ideal has been introduced as an obstruction to linear-width. Moreover, it was already known that mixed search number is equivalent to linear-width. Hence, by combining those results, we obtain a proof of the equivalence between linear tangle and maximal single ideal. This short report gives an alternative proof of the equivalence.

Multipass Streaming Algorithms for Regularized Submodular Maximization

In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.

Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.

Approximating(mB,mP)-Monotone BP Maximization and Extensions

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular(BP)functions with partial monotonicity under a streaming fashion.In this model,elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions.The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible.In this work,a threshold-based streaming algorithm is presented for the BP maximization that attains a(1-k)/(2-k)-O(e)-approximation with O(1/e^(4)1og^(3)(1/s)log(2-k)k/(1-k)^(2))memory complexity,where k denotes the parameter of supermodularity ratio.We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation.We finally investigate this fair model under the streaming fashion and provide a(1-k)^(4)/(2-2k+k^(2))^(2)-O(e)-approximation algorithm.

A Note on Maximizing Regularized Submodular Functions Under Streaming

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.

Bicriteria Algorithms for Approximately Submodular Cover Under Streaming Model

In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear,and the cover function is non-monotone approximately submodular.We study the problem under streaming model and propose three bicriteria approximation algorithms.Firstly,we provide an intuitive streaming algorithm under the assumption of known optimal objective value.The intuitive streaming algorithm returns a solution such that its cover function value is no less thanα(1−ϵ)times threshold,and the cost function is no more than(2+ϵ)^(2)/(ϵ^(2)ω^(2))⋅κ,whereκis a value that we suppose for the optimal solution andαis the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly.Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance,and maintain the same bicriteria approximation ratio.Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio.Additionally,we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.

Structural Properties in a Hub-to-Hub Network Revenue Management Problem

In this paper,the structural properties of revenue management in a hubto-hub airline network is studied.Using a reformulated network flow version of the problem,it is shown that the optimal value has supermodularity,submodularity,and Lconcavity in the network’s capacities dimensions.It is thus deduced that the certainty equivalent control thresholds used in the revenue management problem have monotone properties.These structural properties add important managerial insights into the network revenue management system.

Performance bounds for Nash equilibria in submodular utility systems with user groups

It is shown that for a valid non-cooperative utility system,if the social utility function is submodular,then any Nash equilibrium achieves at least 1/2 of the optimal social utility,subject to a function-dependent additive term.Moreover,if the social utility function is nondecreasing and submodular,then any Nash equilibrium achieves at least 1/(1+c)of the optimal social utility,where c is the curvature of the social utility function.In this paper,we consider variations of the utility system considered by Vetta,in which users are grouped together.Our aim is to establish how grouping and cooperation among users affect performance bounds.We consider two types of grouping.The first type is from a previous paper,where each user belongs to a group of users having social ties with it.For this type of utility system,each user’s strategy maximises its social group utility function,giving rise to the notion of social-aware Nash equilibrium.We prove that this social utility system yields to the bounding results of Vetta for non-cooperative system,thus establishing provable performance guarantees for the social-aware Nash equilibria.For the second type of grouping we consider,the set of users is partitioned into l disjoint groups,where the users within a group cooperate to maximise their group utility function,giving rise to the notion of group Nash equilibrium.In this case,each group can be viewed as a new user with vector-valued actions,and a 1/2 bound for the performance of group Nash equilibria follows from the result of Vetta.But as we show tighter bounds involving curvature can be established.By defining the group curvature cki associated with group i with ki users,we show that if the social utility function is nondecreasing and submodular,then any group Nash equilibrium achieves at least 1/(1+max1≤i≤l cki)of the optimal social utility,which is tighter than that for the case without grouping.As a special case,if each user has the same action space,then we have that any group Nash equilibrium achieves at least 1/(1+ck∗)of the optimal social utility,where k∗is the least number of users among the l groups.Finally,we present an example of a utility system for database-assisted spectrum access to illustrate our results.

Harmonic influence analysis of unified power flow controller based on modular multilevel converter

The unified power flow controller(UPFC)based on modular multilevel converter(MMC) is the most creative flexible ac transmission system(FACTS) device. In theory, the output voltage of the series MMC in MMCUPFC can be regulated from 0 to the rated value. However,there would be relatively large harmonics in the output voltage if the voltage modulation ratio is small. In order to analyze the influence of MMC-UPFC on the harmonics of the power grid, the theoretical calculation method and spectra of the output voltage harmonics of MMC are presented. Subsequently, the calculation formulas of the harmonics in the power grid with UPFC are proposed. Based on it, the influence of UPFC on the grid voltage harmonics is evaluated, when MMC-UPFC is operated with different submodular numbers and voltage modular ratios. Eventually, the proposed analysis method is validated using digital simulation. The study results would provide guideline for the design and operation of MMC-UPFC project.

Approximating Special Social Influence Maximization Problems

Social Influence Maximization Problems(SIMPs)deal with selecting k seeds in a given Online Social Network(OSN)to maximize the number of eventually-influenced users.This is done by using these seeds based on a given set of influence probabilities among neighbors in the OSN.Although the SIMP has been proved to be NP-hard,it has both submodular(with a natural diminishing-return)and monotone(with an increasing influenced users through propagation)that make the problem suitable for approximation solutions.However,several special SIMPs cannot be modeled as submodular or monotone functions.In this paper,we look at several conditions under which non-submodular or non-monotone functions can be handled or approximated.One is a profit-maximization SIMP where seed selection cost is included in the overall utility function,breaking the monotone property.The other is a crowd-influence SIMP where crowd influence exists in addition to individual influence,breaking the submodular property.We then review several new techniques and notions,including double-greedy algorithms and the supermodular degree,that can be used to address special SIMPs.Our main results show that for a specific SIMP model,special network structures of OSNs can help reduce its time complexity of the SIMP.

Budget Allocation for Maximizing Viral Advertising in Social Networks

Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.

An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties

In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.

Approximation Algorithms for Vertex Happiness

We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set functions.The convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of labels.These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation algorithms.For the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>0.For the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△2.We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP relaxation.Lastly,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).

Simultaneous Approximation of Multi-criteria Submodular Function Maximization

Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical significance.In this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization.We address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic corollaries.We offer complete characterization of the symmetric case and partial results on the asymmetric case.

An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.