Logotipo ImpactU
Autor

Expected Performance and Worst Case Scenario Analysis of the Divide-and-Conquer Method for the 0-1 Knapsack Problem.

Acceso Cerrado

Abstract:

In this paper we furnish quality certificates for the Divide-and-Conquer method solving the 0-1 Knapsack Problem: the worst case scenario and estimates for the expected performance. The probabilistic setting is given and the main random variables are defined for the analysis of the expected performance. The efficiency is rigorously approximated for one iteration of the method then, these values are used to derive analytic estimates for the performance of a general Divide-and-Conquer tree. All the theoretical results are verified with statistically suited numerical experiments for a wider illustration of the method.

Tópico:

Optimization and Packing Problems

Citaciones:

Citations: 0
0

Citaciones por año:

No hay datos de citaciones disponibles

Altmétricas:

No hay DOI disponible para mostrar altmétricas

Información de la Fuente:

FuentearXiv (Cornell University)
Cuartil año de publicaciónNo disponible
VolumenNo disponible
IssueNo disponible
PáginasNo disponible
pISSNNo disponible
ISSNNo disponible

Enlaces e Identificadores:

Artículo de revista