Knapsack problem

Summary

The knapsack problem is the following problem in combinatorial optimization: :Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. Applications Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securi

Official source

https://en.wikipedia.org/wiki/Knapsack_problem

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (100)

Related publications

Related people (19)

Related people

Related units (14)

Related units

Related concepts (18)

Related concepts

Related courses (15)

Related courses

Related lectures (50)

Related lectures

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size s and the maximum item value v. We give algorithms that run in time O(n + s³) and O(n + v³) for the Knapsack problem, and in time Õ(n + s^{5/3}) for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants n denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured (min,+)-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Robust Learning-Augmented Caching: An Experimental Study

Adam Teodor Polak

Effective caching is crucial for performance of modern-day computing systems. A key optimization problem arising in caching – which item to evict to make room for a new item – cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions which leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-the-art machine-learned predictors. We show that a straightforward method – blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other – has only a low overhead over a well-performing predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.

PMLR2021

This paper addresses the problem of distributed rate allocation for a class of multicast networks employing linear network coding. The goal is to minimize the cost (for example, the sum rates allocated to each link in the network) while satisfying a multicast rate requirement for each destination in the network. In essence, this paper aims to achieve network capacity while ensuring that the cost of operation (equivalently, the rate allocated per link in the network) is minimal. This paper uses a belief propagation framework to obtain a distributed algorithm for the rate allocation problem. Simulation results are presented to demonstrate the convergence of this algorithm to the optimal rate allocation solution.1

2009

Knapsack problem

It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".

When the answer is "ye

Knapsack and Subset Sum with Small Items

Robust Learning-Augmented Caching: An Experimental Study

Knapsack and Subset Sum with Small Items

Robust Learning-Augmented Caching: An Experimental Study