Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Improved algorithms and analysis for secretary problems and generalizations
Autore:
Ajtai, M; Megiddo, N; Waarts, O;
Indirizzi:
IBM Corp, Almaden Res Ctr, Div Res, Dept K53 B2, San Jose, CA 95120 USA IBM Corp San Jose CA USA 95120 v Res, Dept K53 B2, San Jose, CA 95120 USA Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel Tel Aviv Univ Tel Aviv Israel IL-69978 th Sci, IL-69978 Tel Aviv, Israel Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA Univ Calif Berkeley Berkeley CA USA 94720 omp Sci, Berkeley, CA 94720 USA
Titolo Testata:
SIAM JOURNAL ON DISCRETE MATHEMATICS
fascicolo: 1, volume: 14, anno: 2001,
pagine: 1 - 27
SICI:
0895-4801(2001)14:1<1:IAAAFS>2.0.ZU;2-H
Fonte:
ISI
Lingua:
ENG
Keywords:
dynamic programming; optimal stopping; expected rank maximization;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
18
Recensione:
Indirizzi per estratti:
Indirizzo: Ajtai, M IBM Corp, Almaden Res Ctr, Div Res, Dept K53 B2, 650 Harry Rd, San Jose, CA 95120 USA IBM Corp 650 Harry Rd San Jose CA USA 95120 an Jose, CA 95120 USA
Citazione:
M. Ajtai et al., "Improved algorithms and analysis for secretary problems and generalizations", SIAM J DISC, 14(1), 2001, pp. 1-27

Abstract

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximizethe probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k = 1 are well known. Partial solutions for the rst variant with general k are also known. In contrast, anexplicit solution for the second variant with general k has not been known. It seems that the fact that the expected sum of powers of the ranks of selected items is bounded as n tends to infinity has been known to follow from standard results. We derive our results by obtaining explicit algorithms. For each z greater than or equal to 1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k(z+1)/(z + 1) + C(z) . k(z+0.5) log k, where log k = max {1, log(2) k}, whereas the best possible value at all is k(z+1)/(z + 1) + O(k(z)). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on thetrade-off between the probability of selecting the best object and the expected rank of the selected object.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 02/06/20 alle ore 02:06:06