Performance of trigonometric generating functions on some combinatorial problems

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.

MoreLess

Year of publication:	2005-10
Authors:	NESTEROV, Yu.
Institutions:	Center for Operations Research and Econometrics (CORE), École des Sciences Économiques de Louvain
Subject:	integer programming \| generating functions \| polynomial complexity \| dynamic programming \| knapsack problem

freely available

Full text |

More access options

Check Google Scholar

In German libraries (KVK)

I need help

More details

Extent:	application/pdf
Series:	CORE Discussion Papers.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series UNIVERSITE CATHOLIQUE DE LOUVAIN, Center for Operations Research and Econometrics (CORE) Number 2005069
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005065423