No label defined (Q4458134)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2059840
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2059840 |
Statements
17 March 2004
0 references
knapsack-type problems
0 references
polynomial-time subclasses
0 references
constrained longest paths
0 references
0.9408568
0 references
0.92180395
0 references
0.91492176
0 references
0.90873075
0 references
0.90722334
0 references
0.9045854
0 references
0.9042475
0 references
0.9034874
0 references
The paper deals with interactive knapsack (IK) problems, which are motivated by load clipping problems: variable demand for electricity can be handled by combined production and electricity purchases (by the supplier) as well as by electricity storage (by a group). As prices of electricity may vary substantially, the goal is to minimize the total loss within a period of \(N\) ``hours'', caused by buying electricity (overload) or loosing revenue (underload). If a group can store energy, it can move the overload to the next hours where the overload is cheaper. This is modelled by inserting one item into a knapsack \(i\) and copies into knapsacks \(i+ 1,\dots,i+ c\) (clone); an item can also ``radiate'', that is some portion of the item can be copied into knapsacks \(i- u,\dots,i- 1\) and \(i+ c+ 1,\dots,i+ c+ u\). In the IKHO problem, only one (type of) item is used to be filled into an arrey of \(N\) knapsacks -- each with a specific capacity --, to maximize the total gain within the whole period. By introducing a suitable acyclic graph, the author can show: \(\text{IKHO}\in P\) for \(u= 0\) (no radiation) and fixed \(c\) resp. \(c_{\min}< c< c_{\max}\), and he can develop -- based on constrained longest pathes in acyclic graphs -- a polynomial -- time algorithm in the case, where the total length 1 (of clone and radiation parts) is at most of logarithmic size in the number of knapsacks. In case of \(n\) (types of) items, the (IKO-) problem becomes strongly NP-hard. But for fixed \(n\) and no radiation \((u= 0)\) the author can prove: \(\text{IKO}\in P\), if 1 is of logarithmic size again. The 0-1-multi-dimensional-knapsack-problem (MDKP), where one has to obey \(m> 1\) knapsack restrictions simultaneously, can be polynomially reduced to IKHO and solved by similar methods in cases, where the band matrix has width w at most \(k+ \log m\).
0 references