A new lower bound for the linear knapsack problem with general integer variables

MATHUR, Kamlesh ; VENKATESHAN, Prahalad

In: European journal of operational research, Jg. 178 (2007), Heft 3, S. 738-754

Online academicJournal - print, 1/4 p

Zugriff:

View record from ScienceDirect (Volltext)

It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature.

Titel:	A new lower bound for the linear knapsack problem with general integer variables
Autor/in / Beteiligte Person:	MATHUR, Kamlesh ; VENKATESHAN, Prahalad
Link:	View record from ScienceDirect (Volltext) E-Journal im Bestand der UB Hagen? View record from PASCAL Archive
Zeitschrift:	European journal of operational research, Jg. 178 (2007), Heft 3, S. 738-754
Veröffentlichung:	Amsterdam: Elsevier, 2007
Medientyp:	academicJournal
Umfang:	print, 1/4 p
ISSN:	0377-2217 (print)
Schlagwort:	Control theory, operational research Automatique, recherche opérationnelle Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Recherche operationnelle. Gestion Operational research. Management science Borne inférieure Lower bound Cota inferior Problème NP difficile NP hard problem Problema NP duro Problème sac à dos Knapsack problem Problema mochila Programmation discrète Discrete programming Programación discreta Programmation en nombres entiers Integer programming Programación entera Programmation linéaire Linear programming Programación lineal Discrete optimizations
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Article File Description: text Language: English Author Affiliations: Department of Operations, Weatherhead School of Management, Case Western Reserve University, Cleveland, OH 44106, United States Rights: Copyright 2007 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Operational research. Management

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.