This article is available for purchase or by subscription. See below.
Abstract
|
The original knapsack problem is well known to be NP-complete.
In a multidimensional version, one have to decide whether a
is in the
sumset-sum of a set
.
In this paper, we are going to investigate a communication complexity
problem related to this. We are also going to prove some results about the
special case of the multidimensional knapsack problem, when the set
is in the
form
, where
is a so-called
regular
set for every
.
|
PDF Access Denied
We have not been able to recognize your IP address
44.221.45.48
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
Keywords
subset sums, communication complexity, matching in
bipartite graph
|
Mathematical Subject Classification
Primary: 11B30, 11B39, 11B75
|
Milestones
Received: 27 July 2021
Revised: 21 October 2021
Accepted: 7 November 2021
Published: 17 January 2022
|
|