English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  How to Pack Your Items When You Have to Buy Your Knapsack

Antoniadis, A., Huang, C.-C., Ott, S., & Verschae, J. (2013). How to Pack Your Items When You Have to Buy Your Knapsack. In K. Chatterjee, & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 62-73). Berlin: Springer. doi:10.1007/978-3-642-40313-2_8.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3B54-9 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-9B15-F
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Antoniadis, Antonios1, Author
Huang, Chien-Chung1, Author
Ott, Sebastian2, Author           
Verschae, José1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: In this paper we consider a generalization of the classical knapsack problem. While in the standard setting a fixed capacity may not be exceeded by the weight of the chosen items, we replace this hard constraint by a weight-dependent cost function. The objective is to maximize the total profit of the chosen items minus the cost induced by their total weight. We study two natural classes of cost functions, namely convex and concave functions. For the concave case, we show that the problem can be solved in polynomial time; for the convex case we present an FPTAS and a 2-approximation algorithm with the running time of \mathcalO(n \log n), where n is the number of items. Before, only a 3-approximation algorithm was known. We note that our problem with a convex cost function is a special case of maximizing a non-monotone, possibly negative submodular function.

Details

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: 932795468740665CC1257C600053E9EA-Ott2013
DOI: 10.1007/978-3-642-40313-2_8
BibTex Citekey: Ott2013
 Degree: -

Event

show
hide
Title: 38th International Symposium on Mathematical Foundations of Computer Science
Place of Event: Klosterneuburg, Austria
Start-/End Date: 2013-08-26 - 2013-08-30

Legal Case

show

Project information

show

Source 1

show
hide
Title: Mathematical Foundations of Computer Science 2013
  Abbreviation : MFCS 2013
  Subtitle : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013 ; Proceedings
Source Genre: Proceedings
 Creator(s):
Chatterjee, Krishnendu1, Editor
Sgall, Jiri1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 62 - 73 Identifier: ISBN: 978-3-642-40312-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 8087 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743