Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Antoniadis, Antonios Huang, Chien-Chung Ott, Sebastian Verschae, José dblp dblp dblp dblp Not MPG Author(s): Antoniadis, Antonios Huang, Chien-Chung Verschae, José
 Editor(s): Chatterjee, Krishnendu Sgall, Jiri dblp dblp Not MPII Editor(s): Chatterjee, Krishnendu Sgall, Jiri
 BibTeX cite key*: Ott2013

 Title, Booktitle
 Title*: How to Pack Your Items When You Have to Buy Your Knapsack Booktitle*: Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013

 Event, URLs
 URL of the conference: http://ist.ac.at/mfcs13/ URL for downloading the paper: http://www.mpi-inf.mpg.de/~ott/download/MFCS2013_FULL.pdf Event Address*: Klosterneuburg, Austria Language: English Event Date* (no longer used): Organization: Event Start Date: 26 August 2013 Event End Date: 30 August 2013

 Publisher
 Name*: Springer URL: http://www.springer.com Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 8087 Number: Month: Pages: 62-73 Year*: 2013 VG Wort Pages: ISBN/ISSN: 978-3-642-40312-5 Sequence Number: DOI: 10.1007/978-3-642-40313-2_8

 (LaTeX) 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 $\mathcal{O}(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. Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Ott2013,
AUTHOR = {Antoniadis, Antonios and Huang, Chien-Chung and Ott, Sebastian and Verschae, Jos{\'e}},
EDITOR = {Chatterjee, Krishnendu and Sgall, Jiri},
BOOKTITLE = {Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013},
PUBLISHER = {Springer},
YEAR = {2013},
VOLUME = {8087},
PAGES = {62--73},
SERIES = {Lecture Notes in Computer Science},