A Newton’s method for the continuous quadratic knapsack problem

  • We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in dif- ferent contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n2). Numerical experiments show that in practice the method con- verges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Roberto Cominetti, Walter F. Mascarenhas, Paulo J. S. Silva
DOI:https://doi.org/10.1007/s12532-014-0066-y
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2014
Tag:Software; Theoretical Computer Science
Volume:6
Issue:2
Page Number:19
First Page:151
Last Page:169
Mathematical Programming Computation :MPC 2014 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.