Algoritmos factibles, problemas tratables y la complejidad computacional de una variante del problema de la diversidad máxima
Resumen
La intención de este artículo es dar una demostración formal del carácter NP-duro de una nueva variante del conocido problema de optimización combinatoria de la diversidad máxima, esta nueva variante es denominada problema del máximo promedio. Además se presenta una breve revisión de las nociones y conceptos relacionados con la NP-dureza, y la conjetura P vs.NP, con el fin de comprender la naturaleza de los problemas de optimización, y por qué algunos de ellos se pueden considerar fáciles y otros pueden llamarse difíciles.
Citas
GAREY, M., JOHNSON, D. (1979). "Computers and Intractability: A Guide to the Theory of NP-Completeness". s.1. : W.H. Freeman y Cía.
CLAY MATHEMATICS INSTITUTE. [En línea] [Citado el: 20 de 05 de 2013.] http://www.claymath.org/millennium/.
CARLSON, J. (2013). First Clay Mathematics Institute Millennium Prize Announced Today. [En línea] [Citado el: 22 de 05 de 2013.] http://www.claymath.org/poincare/millenniu mPrizeFull .pdf.
GHOSH. (1996). "Computational aspects of the maximum diversity problem ". 4, s.l.: Elsevier, Operations Research Letters, Vol. 19, págs. 175-181.
MARTÍ, R., SANDOYA, F. GRASP and Path Relinking for the Equitable Dispersion Problem. s.l. : Elsevier, 2012, Computers & Operations Research, págs. 1 -18. http://dx.doi.org/ l O. lO 16/j .cor.2012.04 .005.
PROKOPYEV, O., KONG, N., MARTÍNEZ-TORRES, D. "The equitable dispersion problem" . 197, 2009, European Journal of Operational Research, págs. 59 - 67.
CLAY MATHEMATICS INSTITUTE. [En línea] [Citado el: 20 de 05 de 2013.] http://www.claymath.org/millennium/.
CARLSON, J. (2013). First Clay Mathematics Institute Millennium Prize Announced Today. [En línea] [Citado el: 22 de 05 de 2013.] http://www.claymath.org/poincare/millenniu mPrizeFull .pdf.
GHOSH. (1996). "Computational aspects of the maximum diversity problem ". 4, s.l.: Elsevier, Operations Research Letters, Vol. 19, págs. 175-181.
MARTÍ, R., SANDOYA, F. GRASP and Path Relinking for the Equitable Dispersion Problem. s.l. : Elsevier, 2012, Computers & Operations Research, págs. 1 -18. http://dx.doi.org/ l O. lO 16/j .cor.2012.04 .005.
PROKOPYEV, O., KONG, N., MARTÍNEZ-TORRES, D. "The equitable dispersion problem" . 197, 2009, European Journal of Operational Research, págs. 59 - 67.
