N. Alechina and B. Logan, State space search with prioritised soft constraints, Applied Intelligence, vol.14, issue.3, pp.263-272, 2001.
DOI : 10.1023/A:1011242703014

R. Andonov, V. Poirriez, and S. Rajopadhye, Unbounded knapsack problem: Dynamic programming revisited, European Journal of Operational Research, vol.123, issue.2, pp.394-407, 2000.
DOI : 10.1016/S0377-2217(99)00265-9

A. Apostolico and C. Guerra, The longest common subsequence problem revisited, Algorithmica, vol.21, issue.1-4, pp.315-336, 1987.
DOI : 10.1007/BF01840365

Z. Bai, C. Chao, H. Hwang, and W. Liang, On the variance of the number of maxima in random vectors and its applications, Annals of Applied Probability, vol.8, pp.886-895, 1998.

Z. Bai, H. Hwang, W. Liang, and T. Tsai, Limit Theorems for the Number of Maxima in Random Samples from Planar Regions, Electronic Journal of Probability, vol.6, issue.0, p.41, 2001.
DOI : 10.1214/EJP.v6-76

Z. Bai, H. Hwang, and T. Tsai, Berry-Esseen Bounds for the Number of Maxima in Planar Regions, Electronic Journal of Probability, vol.8, issue.0, p.26, 2003.
DOI : 10.1214/EJP.v8-137

G. , D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, vol.4, pp.235-282, 1994.

R. A. Becker, L. Denby, R. Mcgill, and A. R. Wilds, Analysis of Data from the Places Rated Almanac, The American Statistician, vol.41, issue.3, pp.41-169, 1987.
DOI : 10.2307/2685098

J. L. Bentley, Multidimensional divide-and-conquer, Communications of the ACM, vol.23, issue.4, pp.214-229, 1980.
DOI : 10.1145/358841.358850

J. L. Bentley, K. L. Clarkson, and D. B. Levine, Fast linear expected-time algorithms for computing maxima and convex hulls, Algorithmica, vol.20, issue.2, pp.168-183, 1993.
DOI : 10.1007/BF01188711

J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM, vol.25, issue.4, pp.536-543, 1978.
DOI : 10.1145/322092.322095

J. L. Bentley and M. I. Shamos, Divide and conquer for linear expected time, Information Processing Letters, vol.7, issue.2, pp.87-91, 1978.
DOI : 10.1016/0020-0190(78)90051-0

P. Berman, Z. Zhang, Y. I. Wolf, E. V. Koonin, and W. Miller, Winnowing Sequences from a Database Search, Journal of Computational Biology, vol.7, issue.1-2, pp.293-302, 2000.
DOI : 10.1089/10665270050081531

S. Bespamyatnikh and D. Kirpatrick, Rectilinear 2-center problems, Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), pp.68-71, 1999.

C. Blair, Random inequality constraint systems with few variables, Mathematical Programming, pp.135-139, 1986.
DOI : 10.1007/BF01580644

C. Blair, Random linear programs with many variables and few constraints, Mathematical Programming, pp.62-71, 1986.
DOI : 10.1007/BF01582163

K. L. Clarkson, More output-sensitive geometric algorithms (extended abstract), IEEE 35th Annual Symposium on Foundations of Computer Science, pp.695-702, 1994.

D. D. Cardillo and T. Fortuna, A DEA model for the efficiency evaluation of nondominated paths on a road network, European Journal of Operational Research, vol.121, issue.3, pp.549-558, 2000.
DOI : 10.1016/S0377-2217(99)00053-3

C. A. Coello-coello, D. A. Van-veldhuizen-amd, and G. B. Lamont, Evolutionary Algorithms for Solving Multiobjective Problems, 2002.

R. Daruwala, On Computing the Pareto Optimal Solution Set in a Large Scale Dynamic Network, 2002.

S. K. Das, A. Goswami, and S. S. Alam, Multiobjective transportation problem with interval cost, source and destination parameters, European Journal of Operational Research, vol.117, issue.1, pp.100-112, 1999.
DOI : 10.1016/S0377-2217(98)00044-7

P. Dasgupta, P. P. Chakrabarti, and S. C. Desarkar, Multiobjective Heuristic Search: An Introduction to Intelligent Search Methods for Multicriteria Optimization, 1999.
DOI : 10.1007/978-3-322-86853-4

L. Devroye, Momentenungleichungen f??r Zufallsvariable bei geometrischen Berechnungsverfahren, Computing, vol.1, issue.2, pp.30-111, 1983.
DOI : 10.1007/BF02280782

L. Devroye, A note on the expected time required to construct the outer layer, Information Processing Letters, vol.20, issue.5, pp.255-257, 1985.
DOI : 10.1016/0020-0190(85)90028-6

L. Devroye, A Note on the Expected Time for Finding Maxima by List Algorithms, Algorithmica, vol.23, issue.2, pp.97-108, 1999.
DOI : 10.1007/PL00009256

M. E. Dyer and J. Walker, Dominance in multi-dimensional multiple-choice knapsack problems, Asia-Pacific Journal of Operational Research, vol.15, pp.159-168, 1998.

H. Edelsbrunner and M. H. Overmars, On the equivalence of some rectangle problems, Information Processing Letters, vol.14, issue.3, pp.124-127, 1982.
DOI : 10.1016/0020-0190(82)90068-0

M. Ehrgott, Multicriteria Optimization, 2000.
DOI : 10.1007/978-3-662-22199-0

P. Flajolet and M. Golin, Exact asymptotics of divide-and-conquer recurrences, Lecture Notes in Computer Science, vol.700, pp.137-149, 1993.
DOI : 10.1007/3-540-56939-1_68

T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, Interval finding and its application to data mining, IEICE Transaction on Fundamentals of Electronics Communications and Computer Sciences, pp.80-620, 1997.
DOI : 10.1007/BFb0009481

M. S. Gelfand, L. I. Podolsky, T. V. Astakhova, and M. A. Roytberg, Recognition of Genes in Human DNA Sequences, Journal of Computational Biology, vol.3, issue.2, pp.223-234, 1996.
DOI : 10.1089/cmb.1996.3.223

T. Getachew, M. Kostreva, and L. Lancaster, A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks, RAIRO - Operations Research, vol.34, issue.1, pp.27-47, 2000.
DOI : 10.1051/ro:2000100

M. J. Golin, A provably fast linear-expected-time maxima-finding algorithm, Algorithmica, pp.501-524, 1994.

S. Greco, B. Matarazzo, and R. Slowinski, Rough approximation by dominance relations, International Journal of Intelligent Systems, vol.1, issue.2, pp.153-171, 2002.
DOI : 10.1002/int.10014

R. H. Güting, O. Nurmi, and T. Ottmann, Fast algorithms for direct enclosures and direct dominances, Journal of Algorithms, vol.10, issue.2, pp.170-186, 1989.
DOI : 10.1016/0196-6774(89)90011-4

K. Hakata and H. Imai, Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima, Optimization Methods and Software, pp.233-260, 1998.

A. Hero and G. Fleury, Pareto-optimal methods for gene analysis, preprint, 2002.

R. E. Johnston and L. R. Khan, A note on dominance in unbounded knapsack problems, Asia-Pacific Journal of Operational Research, vol.12, pp.145-160, 1995.

T. Kameda, On the vector representation of the reachability in planar directed graphs, Information Processing Letters, vol.3, issue.3, pp.75-77, 1975.
DOI : 10.1016/0020-0190(75)90019-8

S. Kapoor, Dynamic Maintenance of Maxima of 2-d Point Sets, SIAM Journal on Computing, vol.29, issue.6, pp.1858-1877, 2000.
DOI : 10.1137/S0097539798348365

V. Kathail, S. Aditya, R. Schreiber, B. R. Rau, D. C. Cronquist et al., PICO: automatically designing custom computers, Computer, vol.35, issue.9, pp.9-39, 2002.
DOI : 10.1109/MC.2002.1033026

D. G. Kirkpatrick and R. Seidel, Output-size sensitive algorithms for finding maximal vectors, Proceedings of the first annual symposium on Computational geometry , SCG '85, pp.89-96, 1985.
DOI : 10.1145/323233.323246

D. E. Knuth, Mathematical analysis of algorithms, IFIP Congress, pp.19-27, 1971.

D. E. Knuth, The Art of Computer Programming Sorting and Searching, Second Edition, 1998.

H. T. Kung, F. Luccio, and F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM, vol.22, issue.4, pp.469-476, 1975.
DOI : 10.1145/321906.321910

J. Lillis and C. K. Cheng, Timing optimization for multisource nets: characterization and optimal repeater insertion, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.18, issue.3, pp.322-331, 1999.
DOI : 10.1109/43.748162

H. M. Mahmoud, P. Flajolet, P. Jacquet, and M. Régnier, Analytic variations on bucket selection and sorting, Acta Informatica, vol.36, issue.9-10, pp.735-760, 2000.
DOI : 10.1007/s002360050173

URL : https://hal.archives-ouvertes.fr/inria-00073290

M. Müller, Partial order bounding: A new approach to evaluation in game tree search, Artificial Intelligence, vol.129, issue.1-2, pp.279-311, 2001.
DOI : 10.1016/S0004-3702(01)00085-6

A. M. Odlyzko, Search for the maximum of a random walk, Random Structures and Algorithms, pp.275-295, 1995.

B. O. Neill, The Number of Outcomes in the Pareto-Optimal Set of Discrete Bargaining Games, Mathematics of Operations Research, vol.6, issue.4, pp.571-578, 1980.
DOI : 10.1287/moor.6.4.571

J. Pomerol and S. Barba-romero, Multicriterion Decision in Management, 2000.
DOI : 10.1007/978-1-4615-4459-3

F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, 1985.
DOI : 10.1007/978-1-4612-1098-6

J. H. Reynolds and E. D. Ford, MULTI-CRITERIA ASSESSMENT OF ECOLOGICAL PROCESS MODELS, Ecology, vol.80, issue.2, pp.80-538, 1999.
DOI : 10.1002/for.3980100110

A. L. Rukhin, Admissibility: Survey of a Concept in Progress, International Statistical Review / Revue Internationale de Statistique, vol.63, issue.1, pp.95-115, 1995.
DOI : 10.2307/1403779

S. Sen and N. Gupta, Distribution-sensitive algorithms, Nordic Journal of Computing, vol.6, pp.194-211, 1999.
DOI : 10.1007/BFb0054380

B. S. Stewart, C. C. White, I. Multiobjective, and A. , Multiobjective A*, Journal of the ACM, vol.38, issue.4, pp.775-814, 1991.
DOI : 10.1145/115234.115368

Y. Sun and C. L. Liu, An area minimizer for floorplans with L-shaped regions, Proceedings 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors, pp.383-386, 1992.
DOI : 10.1109/ICCD.1992.276295

G. K. Tayi, D. J. Rosenkrantz, and S. S. Ravi, Path problems in networks with vector-valued edge weights, Networks, pp.34-53, 1999.

H. F. Ting and A. C. Yao, A randomized algorithm for finding maximum with O((log n)2) polynomial tests, Information Processing Letters, vol.49, issue.1, pp.49-88, 1994.
DOI : 10.1016/0020-0190(94)90052-3

Y. Tyutyunov, I. Senina, C. Jost, and R. Arditi, Risk assessment of the harvested pike-perch population of the Azov Sea, Ecological Modelling, vol.149, issue.3, pp.297-311, 2002.
DOI : 10.1016/S0304-3800(01)00478-1

D. A. Van-veldhuizen and G. B. Lamont, Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art, Evolutionary Computation, vol.8, issue.2, pp.125-147, 2000.
DOI : 10.1109/4235.797969

A. Wald, Statistical Decision Functions., Journal of the American Statistical Association, vol.46, issue.253, 1971.
DOI : 10.2307/2280105

A. Warburton, Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems, Operations Research, vol.35, issue.1, pp.70-79, 1987.
DOI : 10.1287/opre.35.1.70

M. Zachariasen, Rectilinear full Steiner tree generation, Networks, pp.33-125, 1999.