Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Feasibility of integer knapsacks

Aliev, Iskander and Henk, Martin 2010. Feasibility of integer knapsacks. Siam Journal of Optimization 20 (6) , pp. 2978-2993. 10.1137/090778043

[img]
Preview
PDF - Published Version
Download (262kB) | Preview

Abstract

Given a matrix $A\in\mathbb{Z}^{m\times n}$ satisfying certain regularity assumptions, we consider the set $\mathcal{F}(A)$ of all vectors $\boldsymbol{b}\in\mathbb{Z}^m$ such that the associated knapsack polytope $P(A,\boldsymbol{b})=\{\boldsymbol{x}\in\mathbb{R}^n_{\geq0}:A\boldsymbol{x}=\boldsymbol{b}\}$ contains an integer point. When $m=1$ the set $\mathcal{F}(A)$ is known to contain all consecutive integers greater than the Frobenius number associated with A. In this paper we introduce the diagonal Frobenius number $\mathrm{g}(A)$ which reflects in an analogous way feasibility properties of the problem and the structure of $\mathcal{F}(A)$ in the general case. We give an optimal upper bound for $\mathrm{g}(A)$ and also estimate the asymptotic growth of the diagonal Frobenius number on average. Read More: http://epubs.siam.org/doi/abs/10.1137/090778043

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Additional Information: Pdf uploaded in accordance with publisher's policy at http://www.sherpa.ac.uk/romeo/issn/1052-6234/ (accessed 27/02/2014).
Publisher: Society of Industrial and Applied Mathematics
ISSN: 1052-6234
Date of First Compliant Deposit: 30 March 2016
Last Modified: 07 Dec 2018 20:29
URI: http://orca.cf.ac.uk/id/eprint/24988

Citation Data

Cited 9 times in Google Scholar. View in Google Scholar

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics