  


On Approximation Algorithms for Concave MixedInteger Quadratic Programming
Alberto Del Pia (delpiawisc.edu) Abstract: Concave MixedInteger Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixedinteger points in a polyhedral region. In this work we describe an algorithm that finds an εapproximate solution to a Concave MixedInteger Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ε, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P = NP. Keywords: mixedinteger quadratic programming; approximation algorithms Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Global Optimization (Theory ) Citation: Submitted manuscript Download: [PDF] Entry Submitted: 05/28/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  