The research of influence propagation in social networks via word-of-mouth processes has been given considerable attention in recent years. Arguably, the most fundamental problem in this domain is influence maximization, where the goal is to identify a seed set of individuals that can trigger a large cascade of influence in the network. While there has been significant progress regarding this problem and its variants, one basic shortcoming of the models is that they lack the flexibility in the way the budget is allocated to individuals. Indeed, budget allocation is a critical issue in advertising and viral marketing. Taking the other point of view, known models allowing flexible budget allocation do not take into account the influence spread in the network. We introduce a generalized model that captures both budgets and influence propagation simultaneously. For the offline setting, we identify a large family of budget-based propagation functions that admit tight approximation guarantee. This family extends most of the previously studied influence models, including the well-known Triggering model. We establish that any function in this family implies an instance of a monotone submodular function maximization over the integer lattice subject to a knapsack constraint. This problem is known to admit an optimal (1-1 e)-approximation. We also study the price of anarchy of the multi-player game that extends the model and establish tight results. For the online setting, in which an unknown subset of agents arrive in a random order and the algorithm needs to make an irrevocable budget allocation in each step, we develop a 1 (15e)-competitive algorithm. This setting extends the secretary problem, and its variant, the submodular knapsack secretary problem. Notably, our algorithm improves over the best known approximation for the latter problem, even though it applies to a more general setting.
@cite_35: We present generalized secretary problems as a framework for online auctions. Elements, such as potential employees or customers, arrive one by one online. After observing the value derived from an element, but without knowing the values of future elements, the algorithm has to make an irrevocable decision whether to retain the element as part of a solution, or reject it. The way in which the secretary framework differs from traditional online algorithms is that the elements arrive in uniformly random order. Many natural online auction scenarios can be cast as generalized secretary problems, by imposing natural restrictions on the feasible sets. For many such settings, we present surprisingly strong constant factor guarantees on the expected value of solutions obtained by online algorithms. The framework is also easily augmented to take into account time-discounted revenue and incentive compatibility. We give an overview of recent results and future research directions.
@cite_18: 
@cite_33: Improved thermosetting sealing materials, for example polyurethane or polysulphide compositions which can be cured in a high frequency alternating electric field, are described which contain electrically non-conducting pigments and or filler whose dielectric constant exceeds 200.
@cite_9: We consider online resource allocation problems where given a set of requests our goal is to select a subset that maximizes a value minus cost type of objective function. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept reject decision as soon as it sees each request. The "profit" of a set of accepted requests is its total value minus a convex cost function of its total size. This problem falls within the framework of secretary problems. Unlike previous work in that area, one of the main challenges we face is that the objective function can be positive or negative and we must guard against accepting requests that look good early on but cause the solution to have an arbitrarily large cost as more requests are accepted. This requires designing new techniques. We study this problem under various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knapsack within a secretary framework. In the absence of any feasibility constraints, we present an O(l) competitive algorithm where l is the number of dimensions; this matches within constant factors the best known ratio for multi-dimensional knapsack secretary.
@cite_29: The Classical Secretary Problem was introduced during the 60's of the 20th century, nobody is sure exactly when. Since its introduction, many variants of the problem have been proposed and researched. In the classical secretary problem, and many of its variant, the input (which is a set of secretaries, or elements) arrives in a random order. In this paper we apply to the secretary problem a simple observation which states that the random order of the input can be generated by independently choosing a random continuous arrival time for each secretary. Surprisingly, this simple observation enables us to improve the competitive ratio of several known and studied variants of the secretary problem. In addition, in some cases the proofs we provide assuming random arrival times are shorter and simpler in comparison to existing proofs. In this work we consider three variants of the secretary problem, all of which have the same objective of maximizing the value of the chosen set of secretaries given a monotone submodular function f. In the first variant we are allowed to hire a set of secretaries only if it is an independent set of a given partition matroid. The second variant allows us to choose any set of up to k secretaries. In the last and third variant, we can hire any set of secretaries satisfying a given knapsack constraint.
@cite_1: In the classical secretary problem, a set S of numbers is presented to an online algorithm in random order. At any time the algorithm may stop and choose the current element, and the goal is to maximize the probability of choosing the largest element in the set. We study a variation in which the algorithm is allowed to choose k elements, and the goal is to maximize their sum. We present an algorithm whose competitive ratio is 1-O(√1 k). To our knowledge, this is the first algorithm whose competitive ratio approaches 1 as k ← ∞. As an application we solve an open problem in the theory of online auction mechanisms.
@cite_6: We consider situations in which a decision-maker with a fixed budget faces a sequence of options, each with a cost and a value, and must select a subset of them online so as to maximize the total value. Such situations arise in many contexts, e.g., hiring workers, scheduling jobs, and bidding in sponsored search auctions. This problem, often called the online knapsack problem, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a randomorder. Hence our problem can be thought of as a weighted version of the classical secretary problem, which we call the knapsack secretary problem. Using the random-order assumption, we design a constant-competitive algorithm for arbitrary weights and values, as well as a e-competitive algorithm for the special case when all weights are equal (i.e., the multiple-choice secretary problem). In contrast to previous work on online knapsack problems, we do not assume any knowledge regarding the distribution of weights and values beyond the fact that the order is random.
@cite_31: 
The classical secretary problem was introduced more than 50 years ago (e.g., @cite_33 ). Since its introduction, many variants and extension of that problem have been proposed and analyzed @cite_1 @cite_6 @cite_35 @cite_9 . The problem that is closest to the problem implied from our online model is the submodular knapsack secretary problem @cite_31 @cite_18 @cite_29 . An instance of this problem consists of a set of @math secretaries that arrive in a random order, each of which has some intrinsic cost. An additional ingredient of the input is a monotone submodular set function that quantifies the value gained from any subset of secretaries. The objective is to select a set of secretaries of maximum value under the constraint that their overall cost is no more than a given budget parameter. Note that our model extends this setting by having a more general influence function that is submodular over the integer lattice. Essentially, this adds another layer of complexity to the problem as we are not only required to decide which secretaries to select, but we also need to assign them budgets.