In the Sequential Selection Problem (SSP), immediate and irrevocable decisions need to be made while candidates from a finite set are being examined one-by-one. The goal is to assign a limited number of @math available jobs to the best possible candidates. Standard SSP variants begin with an empty selection set (cold-starting) and perform the selection process once (single-round), over a single candidate set. In this paper we introduce the Multi-round Sequential Selection Problem (MSSP) which launches a new round of sequential selection each time a new set of candidates becomes available. Each new round has at hand the output of the previous one, i.e. its @math selected employees, and tries to update optimally that selection by reassigning each job at most once. Our setting allows changes to take place between two subsequent selection rounds: resignations of previously selected subjects or and alterations of the quality score across the population. The challenge for a selection strategy is thus to efficiently adapt to such changes. For this novel problem we adopt a cutoff-based approach, where a precise number of candidates should be rejected first before starting to select. We set a rank-based objective of the process over the final job-to-employee assignment and we investigate analytically the optimal cutoff values with respect to the important parameters of the problem. Finally, we present experimental results that compare the efficiency of different selection strategies, as well as their convergence rates towards the optimal solution in the case of stationary score distributions.
Notable variants are those related to , or simply @math -choice, where the DM has to select @math @cite_0 @cite_9 @cite_22 @cite_4 @cite_10 @cite_12 @cite_23 @cite_13 . In that case, the objective set function can be modular ( equivalent to adding up the application of the function to the set elements independently), submodular @cite_25 , supermodular @cite_11 , or sometimes be subject to matroid constraints @cite_14 @cite_1 @cite_19 . Non-modularity introduces interesting set evaluation aspects, such as the complementarity or mutual-enhancement among the selected candidates, which are however out of the scope of this work. Regarding modular objective functions, @cite_15 studies the @math -choice problem with the objective of maximizing the sum of scores of the selected candidates, without assuming prior knowledge of the score distribution. An interesting finding is that the optimal cutoff for that setting does not depend on @math : @math .
@cite_13 @cite_14 @cite_4 @cite_22 @cite_9 @cite_1 @cite_0 @cite_19 @cite_23 @cite_15 @cite_10 @cite_25 @cite_12 @cite_11
2952521477 2061418963 2164792208 2036190740 935564312
Only recently progress has been made in obtaining @math -competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a @math -competitive procedure, and Lachish (2014) later presented a @math -competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably simpler @math -competitive algorithm for the matroid secretary problem. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. Due to the simplicity of our procedure, we are also able to vastly improve on the hidden constant in the competitive ratio. 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. 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. Online auction is the essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the classic secretary problem, is a powerful tool for analyzing such online scenarios which generally require optimizing an objective function over the input. The secretary problem and its generalization the multiple-choice secretary problem were under a thorough study in the literature. In this article, we consider a very general setting of the latter problem called the submodular secretary problem, in which the goal is to select k secretaries so as to maximize the expectation of a (not necessarily monotone) submodular function which defines efficiency of the selected secretarial group based on their overlapping skills. We present the first constant-competitive algorithm for this case. In a more general setting in which selected secretaries should form an independent (feasible) set in each of l given matroids as well, we obtain an O(l log2 r)-competitive algorithm generalizing several previous results, where r is the maximum rank of the matroids. Another generalization is to consider l knapsack constraints (i.e., a knapsack constraint assigns a nonnegative cost to each secretary, and requires that the total cost of all the secretaries employed be no more than a budget value) instead of the matroid constraints, for which we present an O(l)-competitive algorithm. In a sharp contrast, we show for a more general setting of subadditive secretary problem, there is no o(√n)-competitive algorithm and thus submodular functions are the most general functions to consider for constant-competitiveness in our setting. We complement this result by giving a matching O(√n)-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well. In the Secretary Problem, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a random order, and one has to decide on the spot, whether to hire a candidate or continue interviewing. It is well known that the best candidate can be hired with a probability of 1 e (Dynkin, 1963). Recent works extend this problem to settings in which multiple candidates can be hired, subject to some constraint. Here, one wishes to hire a set of candidates maximizing a given set function. Almost all extensions considered in the literature assume the objective set function is either linear or submodular. Unfortunately, real world functions might not have either of these properties. Consider, for example, a scenario where one hires researchers for a project. Indeed, it can be that some researchers can substitute others for that matter. However, it can also be that some combinations of researchers result in synergy (see, e.g, , Science 2010, for a research about collective intelligence). The first phenomenon can be modeled by a submoudlar set function, while the latter cannot. In this work, we study the secretary problem with an arbitrary non-negative monotone function, subject to a general matroid constraint. It is not difficult to prove that, generally, only very poor results can be obtained for this class of objective functions. We tackle this hardness by combining the following: 1.Parametrizing our algorithms by the supermodular degree of the objective function (defined by Feige and Izsak, ITCS 2013), which, roughly speaking, measures the distance of a function from being submodular. 2.Suggesting an (arguably) natural model that permits approximation guarantees that are polynomial in the supermodular degree (as opposed to the standard model which allows only exponential guarantees).