User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Performance of trigonometric generating functions on some combinatorial problems

Primary tabs

download
  • Open access
  • PDF
  • 144.97 K
Nesterov, Yurii [UCL]

In this paper we analyze computational performance of dual trigonometric generating functions on some integer programming problems. We show that if the number of equality constraints is fixed, then this technique allows to solve the problems in time, which is polynomial in the dimension of the space of variables.

Document type Document de travail (Working Paper)
Access type Accès libre
Publication date 2005
Collection CORE Discussion Papers - 2005/69
Affiliation UCL - CORE - Center for Operations Research and Econometrics
Keywords Integer programming ; Generating functions ; Polynomial complexity ; Dynamic programming ; Knapsack problem
Links
Bibliographic reference Nesterov, Yurii. Performance of trigonometric generating functions on some combinatorial problems. CORE Discussion Papers ; 2005/69 (2005)
Permanent URL http://hdl.handle.net/2078.1/4665