Search

In order to develop a suitable washing mode for knapsack, mechanical agitation (1), water bath vibration (2), ultrasonic (3), micro-nano bubble (4) and complex washing mode of the two were systematically investigated. Results showed that regardless of fabric, the washing efficiency of composite washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micro-nano bubble (1 + 4)}, was highest among all washing modes. Moreover, the decrease of stiffness, tensile strength, smoothness and micro-morphology of knapsack by using complex washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micro-nano bubble (1 + 4)} significantly lower than that of mechanical agitation. This indicated that mechanical agitation was the key to remove stain, micro-nano bubbles and ultrasound only assisted its removal. But the addition of micronano bubbles and ultrasound was helpful to improve the washing efficiency and reduce the performance degradation caused by washing mode of mechanical agitation. Complex washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micronano bubble (1 + 4)} was optimal washing combination for knapsack, especially the composite mode of mechanical agitation + ultrasonic (1 + 3), due to its ability to remove residual stains in the inner layer and slit. Moreover, the complex washing mode was also more environmental-friendly and sustainable, compared to other washing mode, because of washing time and detergent dosage reducing occurred by its high washing efficiency. The results were not only helpful to guide manufacturers of washing machine to develop a program dedicated to the daily washing and care knapsack, but also provided scientific care guidance and optimization ideas for subsequent research and applications. [ABSTRACT FROM AUTHOR]

In order to develop a suitable washing mode for knapsack, mechanical agitation (1), water bath vibration (2), ultrasonic (3), micro-nano bubble (4) and complex washing mode of the two were systematically investigated. Results showed that regardless of fabric, the washing efficiency of composite washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micro-nano bubble (1 + 4)}, was highest among all washing modes. Moreover, the decrease of stiffness, tensile strength, smoothness and micro-morphology of knapsack by using complex washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micro-nano bubble (1 + 4)} significantly lower than that of mechanical agitation. This indicated that mechanical agitation was the key to remove stain, micro-nano bubbles and ultrasound only assisted its removal. But the addition of micro-nano bubbles and ultrasound was helpful to improve the washing efficiency and reduce the performance degradation caused by washing mode of mechanical agitation. Complex washing mode {mechanical agitation + ultrasonic (1 + 3), mechanical agitation + micro-nano bubble (1 + 4)} was optimal washing combination for knapsack, especially the composite mode of mechanical agitation + ultrasonic (1 + 3), due to its ability to remove residual stains in the inner layer and slit. Moreover, the complex washing mode was also more environmental-friendly and sustainable, compared to other washing mode, because of washing time and detergent dosage reducing occurred by its high washing efficiency. The results were not only helpful to guide manufacturers of washing machine to develop a program dedicated to the daily washing and care knapsack, but also provided scientific care guidance and optimization ideas for subsequent research and applications. [ABSTRACT FROM AUTHOR]

The Recency, Frequency, and Monetary model, also known as the RFM model, is a popular and widely used business model for determining beneficial client segments and analyzing profit. It is also recommended and frequently used in superstores to identify customer segments and increase profit margins. Later, the Length, Recency, Frequency, and Monetary model, also known as the LRFM model, was introduced as an improved version of the RFM model to identify more relevant and exact consumer groups for profit maximization. Superstores have a varying number of different products. In RFM and LRFM models, the relationship between profit and purchased quantity has never been investigated. Therefore, this paper proposed an efficient customer segmentation model, namely LRFMV (Length, Recency, Frequency, Monetary and Volume) and studied the profit-quantity relationship. A new dimension V (volume) has been added to the existing LRFM model to show a direct profit-quantity relationship in customer segmentation. The V stands for volume, which is derived by calculating the average number of products purchased by a frequent superstore client in a single day. The data obtained from feature extraction of the LRMFV model is then clustered by using conventional K-means, K-Medoids, and Mini Batch K-means methods. The results obtained from the three algorithms are compared, and the K-means algorithm is chosen for the superstore dataset of the proposed LRFMV model. All clusters created using these three algorithms are evaluated in the LRFMV model, and a close relationship between profit and volume is observed. A clear profit-quantity relationship of items has yet not been seen in any prior study on the RFM and LRFM models. Grouping customers aiming at profit maximization existed previously, but there was no clear and direct depiction of profit and quantity of sold items. This study applied unsupervised machine learning to investigate the patterns, trends, and correlations between volume and profit. The traits of all the clusters are analyzed by the Customer-Classification Matrix. The LRFMV values, larger or less than the overall average for each cluster, are identified as their traits. The performance of the proposed LRFMV model is compared with the legacy RFM and LRFM customer segmentation models. The outcome shows that the LRFMV model creates precise customer segments with the same number of customers while maintaining a greater profit. Author summary: Why was this study done?: Superstore business has been booming in the last decades. In the FY-2017, retail revenue of the top 250 superstores was 4,530,059 million USD which achieved 5.7% economic growth [1]. The Length, Recency, Frequency, and Monetary model, also known as the LRFM model, was introduced as an improved version of the RFM model to identify more relevant and exact consumer groups for profit maximization. However, there exists a substantial association between the purchase quantity and revenue generation that had been overlooked in earlier models. In this research, we introduced the LRFMV model, an improved version of existing business models for superstores, to further assess how much revenue boost and marketing strategy can be developed for the superstore industry and contribute to both technical sectors and the business world. In this research, we searched for a new way to utilize the segmentation model based on the scoring procedure and encountered how a business based matrix can employ them to have a substantial influence on the existing collaborative business and technology sector. What did the researchers do and find?: We proposed an efficient customer segmentation model, LRFMV and tried to observe the profit-quantity relationship. A new dimension V (volume) has been added to the existing LRFM model in order to show a direct profit-quantity relationship. Here, the V stands for volume, which was derived by calculating the average number of products purchased by a frequent superstore client in a single day. To get the final average as volume in a specified time frame, the previously found average amount was divided by total days in a limited period of time of visitation of that customer. Quantity of purchased goods refers to the average amount of procured product by repeatedly going customers. Superstores have a varying number of different products with the record of being bought in different quantities multiple times on the same day by a specific customer. In RFM and LRFM models, the relationship between profit and purchased quantity and how they can contribute to an effective customer behavioral analysis was not investigated and evaluated. What do these findings mean?: It is visible that a large volume of purchased products positively influences the profit maximization of a superstore. The establishment of the proposed model will assist superstores in generating more profit and performing comprehensive business analysis by helping to find the most profitable group of customers. [ABSTRACT FROM AUTHOR]

This study presents a boxing match algorithm (BMA) as a new efficient meta-heuristic method to solve numerical optimization and NP-hard problems, such as knapsack. The proposed algorithm finds the best position (i.e., best solution) in the ring during the match (i.e., feasible solutions) through a simulation of the boxer's behavior, who can attract good support from his coach and fans to defeat his rival. The proposed algorithm is seeking good solutions by dividing the solution space into different sections and generating new solutions in each section through a semi-zigzag search. This division causes a proper and targeted search in the solution space to reach an efficient solution. Also, the unique boxer's movement in the ring (generating new solutions) enables the proposed BMA to give an acceptable level of performance in exploring the problem space. Several unconstrained mathematical, knapsack, and engineering benchmark problems undergo a standard test designed to confirm the powerful performance of the proposed BMA. A wide variety of complex numerical problems are solved and analyzed by a comparison between the results obtained from the test and the other well-known optimization methods. Quantitative data also indicate the proper performance of the proposed algorithm compared to the other ones. The results show that this algorithm can achieve 95% and 100% optimal solutions in 20 mathematical benchmark functions and eight examples of the knapsack problem, respectively. [ABSTRACT FROM AUTHOR]

In the study, it was investigated the ejaculation ability and semen quality of drones, according to feeding with pollen in different periods. In the first step of the study, 16 %, 32 %, 47 %, 63 %, 79 %, and 100 % feeding periods were applied to the drones, for investigating the effect on ejaculation ability, and the semen quality of drones was investigated. While investigating these feeding period effects “0-1”, bonded, and unbounded knapsack optimization problems were used. After the most effective feeding period was determined, this period was applied to the traveling salesman and liquid storage tank problems in the second step of the study. In the analysis of the traveling salesman problem, it was determined the shortest way between two cities. Analysis of the liquid storage tank problem, it was determined the minimum connector areas. As a result, the analysis results showed that the performance of the artificial bee colony algorithm is very good while solving too complex engineering optimization problems. [ABSTRACT FROM AUTHOR]

We consider a two-sided streaming service platform that generates revenues by charging users a subscription fee for unlimited access to the content and compensates content providers (artists) through a revenue-sharing allocation rule. Platform users are heterogeneous in both their overall consumption and the distribution of their consumption over different artists. We study two primary revenue allocation rules used by market-leading music streaming platforms—pro-rata and user-centric. With pro-rata, artists are paid proportionally to their share of the overall streaming volume, whereas with user-centric, each user's subscription fee is divided proportionally among artists based on the consumption of that user. We characterize when these two allocation rules can sustain a set of artists on the platform and compare them from both the platform's and the artists' perspectives. In particular, we show that, despite the cross-subsidization between low- and high-streaming-volume users, the pro-rata rule can be preferred by both the platform and the artists. Furthermore, the platform's problem of selecting an optimal portfolio of artists is NP-complete. However, by establishing connections to the knapsack problem, we develop a polynomial time approximation scheme (PTAS) for the optimal platform's profit. In addition to determining the platform's optimal revenue allocation rule in the class of pro-rata and user-centric rules, we consider the optimal revenue allocation rule in the class of arbitrary rules. Building on duality theory, we develop a polynomial time algorithm that outputs a set of artists so that the platform's profit is within a single artist's revenue from the optimal profit. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2022.4307. [ABSTRACT FROM AUTHOR]

The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models (S M K N) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of S M K N to show the performances of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we extend the maximal independent set problem to two-stage stochastic case: given an independence system associated with one deterministic weight function and a random weight function, the goal is to find two nonoverlapping independent subsets from these two stages with the maximum total weight. In this paper, we study the submodularity of three kinds of two-stage independent set problems with max-weight. When the independent set problem is a matroid constraint, we can show its submodularity. However, neither submodular nor supermodular maximization problem can be obtained for the knapsack independent set problem by designing a counterexample. At last, we show that the robust two-stage stochastic maximum-weight uniform matroid problem can be formulated as a γ -submodular problem with cardinality constraint and also give a lower bound for γ. • The submodularity of two-stage stochastic matroid problem with maximum-weight is studied using properties of bases and the circuits in matroids. • An instance of two-stage stochastic knapsack problem which is not a submodular or supermodular maximization problem is proposed. • The robust two-stage stochastic max-weight problem with cardinality constraint can be formulated as a weakly submodular maximization problem. [ABSTRACT FROM AUTHOR]

The knapsack problem is one of the combinational optimization issues. This problem is an NP-hard problem. Soft computing methods, including the use of metaheuristic algorithms, are one way to deal with these types of problems. The standard Giza Pyramids Construction (GPC) algorithm is the first ancient-inspired algorithm that is published recently. In this paper, a binary version of the GPC algorithm for solving the 0-1 knapsack problem is proposed. For this purpose, this study uses both accumulative and multiplicative penalty functions as the objective function to determine infeasible solutions. To compare the performance, thirty different datasets have been created and the proposed algorithm has been compared with four popular and state-of-the-art algorithms. Statistical analysis has been used to find a significant difference in the performance of algorithms. The results and statistical analysis show that the proposed algorithm performs better than other metaheuristic algorithms. [ABSTRACT FROM AUTHOR]

They first characterize the families of graphs for which the graph-restricted game inherits the properties of strong compromise admissibility or compromise stability from the original game. This special issue is a tribute to Professor Francesc Carreras on the occasion of his 70th birthday. The special issue underlines the dedication, illusion, and enthusiasm that Francesc Carreras has put into every one of his research works. Essays in game theory in tribute to Francesc Carreras - SING 15. [Extracted from the article]

In the knapsack problem a group of agents want to fill a knapsack with several goods. Two issues must be considered. The first is to decide optimally what goods to select for the knapsack. This issue has been studied in many papers in the literature on Operations Research and Management Science. The second issue is to divide the total revenue among the agents. This issue has been studied in only a few papers, and this is one of them. For each knapsack problem we consider three associated cooperative games. One of them (the pessimistic game) has already been considered in the literature. The other two (realistic and optimistic games) are defined in this paper. The pessimistic and realistic games have non-empty cores but the core of the optimistic game could be empty. We then follow the axiomatic approach. We propose two rules: The first is based on the optimal solution of the knapsack problem. The second is the Shapley value of the so called optimistic game. We offer axiomatic characterizations of both rules. [ABSTRACT FROM AUTHOR]

Aiming at the multibox 3D packing problem of heterogeneous extrudable items in e-commerce retail department stores, the optimization goal is to select appropriate packaging materials for packing all items in the order. On this basis, the number of packaging materials used is the least and the space utilization rate is high. A heuristic algorithm is designed. Firstly, the items are sorted in descending order according to volume, and then the items are boxed according to the rule of "layer generation." In order to verify the feasibility and effectiveness of the algorithm, the data provided by a large domestic e-commerce platform are used to analyse and compare the space utilization of packaging materials under the conditions of no extrusion operation and extrusion operation. The feasibility and effectiveness of the algorithm in the packaging and delivery link in the storage field of e-commerce retail department stores are proved. [ABSTRACT FROM AUTHOR]

The multiple knapsack problem is a well-studied combinatorial optimization problem with several practical and theoretical applications. It consists of packing some subset of n items into m knapsacks such that the total profit of the chosen items is maximum. A new formulation of the problem is presented, where a Lagrangian relaxation is derived, and we prove that it dominates the commonly used relaxations for this problem. We also present a Dantzig-Wolfe decomposition of the new formulation that we solve to optimality using a branch-and-price algorithm, where its main advantage comes from the fact that it is possible to control whether an item is included in some knapsack or not. An improved algorithm for solving the resulting packing subproblems is also introduced. Computational experiments then show that the new approach achieves state-of-the-art results. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) [Grants 2017-06054 and 2021-04037]. This support is gratefully acknowledged. [ABSTRACT FROM AUTHOR]

With an emerging development in transport technologies, many applications in vehicular environments access roadside unit (RSU) services for tasks offloading. These applications use different types of paid services (e.g., communication, WiFi, and computing nodes) for their execution. The vehicular fog cloud computing (VFCN) is a cooperative computing environment to handle vehicle applications' mobility and resource allocation. However, the aforementioned collaborative VFCN environment still suffers from mobility and security issues in the existing systems. To address the aforementioned issues, in this work we present a cost-efficient and secure VFCN which consists of a mobility-aware multi-scenario offloading phase (MAMSOP) to deal with the mobility and offloading costs. The objective of the work is to execute applications with minimum delays and costs in a secure way. For the security concern, we propose a security scheme based on fully-homomorphism encryption, which encrypts and decrypts data locally and involves computation on encrypted data rather than decrypting it into its original form. As most of the applications have deadline and mobility constraints, so we propose the fully polynomial-time approximation scheme (FPTAS) based search task scheduling (STS) to ensure the execution of all applications within their given constraints. The goal of STS-FPTAS is to determine the delay and cost-aware scheduling into knapsack-aware resources. The knapsack allows all tasks to be allocated to the available length of resources. The results show that the proposed work optimizes the costs by 40% compared to existing systems. [ABSTRACT FROM AUTHOR]

The companies increasingly need to adopt strategies that improve their decision-making, and Operational Research is one of them. Operational Research aims to represent, through mathematical models, real-life problems offering viable solutions and for this it has numerous techniques that provide organizations to achieve economies of significant scales. This article aims to present a practical application of one of these techniques, the linear programming, applied in the making of Christmas food parcel. The article aims to maximize the sales revenue of the food parcel by controlling the items that compose them and performing the possible resupplies if there were missing items in stock. This study is justified by the fact that companies working in this segment do not have an academic reference in this subject. From its construction, it was noticed that the model presented concrete results, its use and interpretation of easy understanding to the employee of the supply sector, and mainly by its daily monitoring and financial result. [ABSTRACT FROM AUTHOR]

With the rapid development of virtual reality (VR) technology, this paper proposes an access point (AP) correlation method based on VR user behavior awareness to address the problem of how current AP correlation methods only focus on the performance improvements of ordinary users and ignore the impact of VR user behavior on service quality. This paper analyzes the AP association method under the coverage scenario of a multi-access point (multi-AP) scenario environment and controls the performance improvement of VR user APs or APs under the access controller (AC) by association. Firstly, the VR network application scenario and system model were constructed, and secondly, the user behavior was sensed by analyzing the viewing habits of users. Then, the VR user association problem based on VR user behavior perception was transformed into a "many-to-many" matching problem between VR user devices and APs, and the generalized multidimensional multiple choice knapsack (GMMKP) model was established to solve the problem using the backpack problem theory; the suboptimal solution algorithm was selected to obtain the best VR user AP association strategy. The experimental results show by simulation that the proposed algorithm in this paper performed better in terms of the AP load balancing and average network download latency compared to the comparison algorithms. [ABSTRACT FROM AUTHOR]

This study investigates the application of the Black Hole algorithm (BH) for solving 0–1 knapsack problems. Knapsack problem is a classic and famous problem for testing and analyzing the behavior of optimization and meta-heuristic algorithms. There is no single algorithm which is suitable for all types of the knapsack problem. So it is an open research area to solve knapsack problem using novel optimization algorithms efficiently. BH algorithm is one of the most recent nature-inspired algorithms that is inspired by the black hole phenomenon. Like other population-based algorithms, the black hole algorithm starts with an initial population of candidate solutions to an optimization problem and an objective function that is calculated for them. At each iteration of the Black hole algorithm, the best candidate is selected to be the black hole, and others called stars. If a star gets too close to the black hole, it will be swallowed by the black hole and is gone forever. Computational experiments with a set of large-scale instances show that the BH algorithm can be an efficient alternative for solving 0–1 knapsack problems. The results show that the algorithm can find high quality solutions in less time compared to similar meta-heuristic approaches. Based on the obtained results it is clear that BH algorithm is a stable algorithm as the standard deviation of finding solutions in different runs is smaller than other test algorithms.

0-1 Knapsack problem (KP) is NP-hard. Approximate solution is vital for solving KP exactly. In this paper, a fast polynomial time approximate solution (FPTAS) is proposed for KP. FPTAS is a local search algorithm. The best approximate solution to KP can be found in the neighborhood of the solution of upper bound for exact k-item knapsack problem (E-kKP) where k is near to the critical item s. FPTAS, in practice, often achieves high accuracy with high speed in solving KP. The computational experiments show that the approximate algorithm for KP is valid. [ABSTRACT FROM AUTHOR]

A flip-swap language is a set S of binary strings of length n such that S ∪ { 0 n } is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of k -ary Dyck words, lattice paths with at most k flaws, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-Gray code when listed in binary reflected Gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flip-swap languages in O (n) -amortized per string, except for prefix normal words of length n which require O (n 1.864) -amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovszki (2008) [35]. [ABSTRACT FROM AUTHOR]

Dynamic programming approach was designed in year 1950's by mathematician Richard Bellman. Dynamic programming approach works in bottom up fashion, it first divide the problem in small overlapped sub problems and then solve them starting from the smallest one and store the solution in a table. The main idea of dynamic programming is a recurrence relation which relates the solution of previous sub problems with the current instance of the problem. Step wise it increases the size of the problem and finally reached to original initial problem. 0/1 knapsack is one of the popular problem solved by using dynamic programming approach, this problem can be used to solve many problem like optimum job scheduling. strategy selection. resource allocation. policy making and many more. This paper presents one of such application of 0/1 knapsack problem in best strategics selection to optimize the objective achievements. [ABSTRACT FROM AUTHOR]

The multiple knapsack problem (0/1-mKP) is a valuable NP-hard problem involved in many science-and-engineering applications. In current research, there exist two main approaches: 1. the exact algorithms for the optimal solutions (i.e., branch-and-bound, dynamic programming (DP), etc.) and 2. the approximate algorithms in polynomial time (i.e., Genetic algorithm, swarm optimization, etc.). In the past, the exact-DP could find the optimal solutions of the 0/1-KP (one knapsack, n objects) in O(nC). For large n and massive C, the unbiased filtering was incorporated with the exact-DP to solve the 0/1-KP in O(n + C′) with 95% optimal solutions. For the complex 0/1-mKP (m knapsacks) in this study, we propose a novel research track with hybrid integration of DP-transformation (DPT), exact-fit (best) knapsack order (m!-to-m2 reduction), and robust unbiased filtering. First, the efficient DPT algorithm is proposed to find the optimal solutions for each knapsack in O([n2,nC]). Next, all knapsacks are fulfilled by the exact-fit (best) knapsack order in O(m2[n2,nC]) over O(m![n2,nC]) while retaining at least 99% optimal solutions as m! orders. Finally, robust unbiased filtering is incorporated to solve the 0/1-mKP in O(m2n). In experiments, our efficient 0/1-mKP reduction confirmed 99% optimal solutions on random and benchmark datasets (n δ 10,000, m δ 100). [ABSTRACT FROM AUTHOR]

Currently, most edge-based Deep Reinforcement Learning (Deep-RL) applications have been deployed in the edge network, however, their mainstream studies are still short of adequate considerations on its limited compute and bandwidth resources. In this paper, we investigate the near on-policy of actions taking in distributed Deep-RL architecture, and propose a "hybrid near on-policy" Deep-RL framework, called Coknight , by leveraging a game-theory based DNN partition approach. We first formulate the partition problem into a variant of knapsack problem in device-edge setting, and then transform it into a potential game with a formal proof. Finally, we show the problem is NP-complete whereby an efficient distributed algorithm based on the potential game theory is developed from device perspective to achieve fast and dynamic partitioning. Coknight not only significantly improves the resource efficiency of the Deep-RL but also allows the inference to enforce the scalability of the actor policy. We prototype the framework with extensive experiments to validate our findings. The experimental results show that with the premise of a rapid convergence guarantee, Coknight , compared with Seed-RL , can reduce GPU utilization by 30% while providing large-scale scalability. • Leverage the DNN partition technology in the device-edge settings to accelerate DRL. • Formulate partition problem as a knapsack problem and prove its NP-Completeness. • Transform the problem into a multi-player game and prove it is a potential game. • Design a dynamic algorithm with polynomial time complexity for DNN partition. • Implement the framework to conduct physical tests and large-scale simulation studies. [ABSTRACT FROM AUTHOR]

In the edge computing environment, Internet of Things (IoT) application service providers can rent resources from edge servers to cache their service items such as datasets and code libraries, and thus significantly reducing the service request latency and the core network traffic. Since IoT service providers need to pay for the rented edge computing resources, it is essential to find a dynamical service caching strategy to minimize the service cost while optimizing the performance objective such as service latency reduction. However, most of the existing studies either overlooked the problem of collaborative service caching or failed to consider the system's long-term service cost and latency. In this paper, to address such a problem, we coordinate multiple edge servers to cache service items and formulate the collaborative service caching problem using a multi-agent multi-armed bandit model. Furthermore, we propose a utility-aware collaborative service caching (UACSC) scheme based on a multi-agent reinforcement learning. The UACSC scheme can coordinate multiple edge servers to make a dynamic joint caching decision, aiming at maximizing the system's long-term utility. To evaluate the performance of our proposed scheme, we implement four representative baseline algorithms and compare them with six different performance metrics. In addition, a real-world case study is also presented to demonstrate the effectiveness of the UACSC scheme. Comprehensive experimental results show that the UACSC scheme can effectively coordinate multiple edge servers to cache service items, and achieve higher service latency reduction and lower service cost compared with other baseline algorithms. • A new problem formulation for the dynamic collaborative service caching at the edge. • Aim to maximize the long-term system utility defined by the service cost and latency reduction. • A new multi-agent reinforcement learning based utility-aware service caching scheme. [ABSTRACT FROM AUTHOR]

In this paper, we have proposed a stochastic Knapsack Problem (KP) based mathematical model for small-scale vegetable sellers in India and solved it by an advanced Genetic Algorithm. The knapsack problem considered here is a bounded one, where vegetables are the objects. In this model, we have assumed that different available vegetables (objects) have different weights (that are available), purchase costs, and profits. The maximum weight of vegetables that can be transported by a seller is limited by the carrying capacity of the vegetable carrier and the business capital of the seller is also limited. The aim of the proposed mathematical model is to maximize the total profit of the loaded/traded items, with a set of predefined constraints on the part of the vegetable seller or retailer. This problem has been solved in a Type-2 fuzzy environment and the Critical Value (CV) reduction method is utilized to defuzzify the objective value. We have projected an improved genetic algorithm based approach, where we have incorporated two features, namely refinement and immigration. We have initially considered benchmark instances and subsequently some redefined cases for experimentation. Moreover, we have solved some randomly generated proposed KP instances in Type-2 fuzzy environment. [ABSTRACT FROM AUTHOR]

Metaheuristic algorithms are solution approaches to solve optimization problems by repeating some algorithmic steps while searching the solution space. The strategy of the metaheuristic includes two basic tactics; exploration for escaping the local optimum and exploitation for the global optimum. The number of solutions while exploring the solution space can be used to classify metaheuristics. If the metaheuristic uses only one solution to generate a new solution, we call it the single-solution-based metaheuristic. Simulated annealing, iterated local search, adaptive large neighborhood search, iterated greedy, local search, and tabu search are examples of single-solution-based metaheuristics. Most of these metaheuristics use an acceptance criterion to whether accept the newly generated solution instead of the incumbent solution to escape from the local optimal. The most used acceptance criterion in the literature is the Metropolis criterion or simulated annealing-like acceptance criterion that decides whether accept the new solution by calculating its acceptance probability. In this study, we propose a fuzzy rule-based acceptance criterion that fuzzies the inputs of the metaheuristic within a fuzzy inference system to create the decision output about the acceptance. The proposed new acceptance criterion is compared with the well-known probabilistic approach in the experimental study with traveling salesman problem, multidimensional knapsack problem, single machine weighted earliness/tardiness problem, linear regression problem, and two continuous optimization problems. The statistical analyses reveal that the number of acceptance solutions while using the proposed acceptance criterion is less than the probabilistic one has but the metaheuristic performance increases with the proposed criterion. Additional analyses are made to explain why the fuzzy criterion convergences better to the global optimum than the probabilistic criterion. [ABSTRACT FROM AUTHOR]

problems. Many different experiments have shown that the evolutionary algorithm Strength Pareto Evolutionary Algorithm 2 (SPEA2) outperforms other approaches, and this makes it an excellent candidate for inclusion in the final design. According to Strength, one of SPEA2's core concepts, the population is sorted into niches based on the Pareto Front idea. With regard to outcomes this technique has a flaw that is mitigated by adding a fitness density estimator. Weakness in Strength is addressed with an approach called Strength by objective, which aims to include solution who do not dominate or are dominated by others inside the process. In this paper, the results will show a clear superiority of the proposed method comparing with the original method in solving the multi-objective Knapsack problem using three sizes of the Knapsack and the problem size of 750 items which is generated randomly. The comparison results between the proposed method and the other algorithms show outperformance of the Proposed algorithm using the dominance inductor showed the superiority of the proposed algorithm by a percentage of more than 1 %, Thanks to a highly diverse population and the inclusion of solutions that can be improved, the (SPEA2) algorithm's performance has been vastly enhanced by the Objective sorting mechanism, [ABSTRACT FROM AUTHOR]

Copyright of Telecommunication Engineering is the property of Telecommunication Engineering and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We consider the Subset-Sums Ratio Problem (SSR), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to 1 as possible, and we introduce a family of variations of SSR that capture additional meaningful requirements. Our main contribution is a generic framework that yields a fully polynomial time approximation scheme (FPTAS) for problems in this family that meet certain conditions. We use our framework to design explicit FPTASs for two such problems, namely Two-Set Subset-Sums Ratio and Factor-r Subset-Sums Ratio , with running time O (n 4 / ε) , which coincides with the best known running time for the original SSR problem [18]. • We define two families of variations of Subset-Sums Ratio problems that are able to capture additional restrictions. • We provide a method to obtain an FPTAS for any problem in these families that meets certain conditions. • We present FPTASs for two variations of Subset-Sums Ratio , namely 2-Set SSR and Factor-r SSR. [ABSTRACT FROM AUTHOR]

Knapsack problem (KP) is a representative combinatorial optimization problem that aims to maximize the total profit by selecting a subset of items under given constraints on the total weights. In this study, we analyze a generalized version of KP, which is termed the generalized multidimensional knapsack problem (GMDKP). As opposed to the basic KP, GMDKP allows multiple choices per item type under multiple weight constraints. Although several efficient algorithms are known and the properties of their solutions have been examined to a significant extent for basic KPs, there is a paucity of known algorithms and studies on the solution properties of GMDKP. To gain insight into the problem, we assess the typical achievable limit of the total profit for a random ensemble of GMDKP using the replica method. Our findings are summarized as follows: (1) when the profits of item types are normally distributed, the total profit grows in the leading order with respect to the number of item types as the maximum number of choices per item type x max increases while it depends on x max only in a sub-leading order if the profits are constant among the item types. (2) A greedy-type heuristic can find a nearly optimal solution whose total profit is lower than the optimal value only by a sub-leading order with a low computational cost. (3) The sub-leading difference from the optimal total profit can be improved by a heuristic algorithm based on the cavity method. Extensive numerical experiments support these findings. [ABSTRACT FROM AUTHOR]

The Internet of Things ecosystem pertains to the web-enabled connected devices that operate built-in processors to record, send, and act on information from their surroundings via embedded communication hardware. IoT applications span from education, healthcare to self-driving cars. The high delay supplied through the connecting network to the data centers and huge data traffic can cause the system to become congested. Hence, the cloud is not suggested for the delay-sensitive applications and it is extremely difficult to provide educational applications, particularly in a mix of cloud and fog conditions. Fog computing was created to address this problem and improve time-sensitive applications by considering quality of service (QoS). The allocation of resources and scheduling of tasks are challenging issues for IoT applications in a fog environment. The resources are required for each educational application that includes several modules to run. In this paper, we used Weighted Greedy Knapsack (WGK) based algorithm for the resource allocation to the modules/components in the fog system. We have considered the smart parade application to provide certain services/resources and the proposed method was experimented in iFogSim. The proposed method shows a better energy consumption and execution cost than that of the concurrent, First-Come-First-Served (FCFS) and Delay-Priority algorithms. [ABSTRACT FROM AUTHOR]

We introduce a regret-based fitness assignment strategy for evolutionary algorithms to find Nash equilibria in noncooperative simultaneous combinatorial game theory problems where it is computationally intractable to enumerate all decision options of the players involved in the game. Applications of evolutionary algorithms to non-cooperative simultaneous games have been limited due to challenges in guiding the evolutionary search toward equilibria, which are usually inferior points in the objective space. We propose a regret-based approach to select candidate decision options of the players for the next generation in a multipopulation genetic algorithm called Regret-Based Nash Equilibrium Sorting Genetic Algorithm (RNESGA). We show that RNESGA can converge to multiple Nash equilibria in a single run using two- and three- player competitive knapsack games and other games from the literature. We also show that pure payoff-based fitness assignment strategies perform poorly in three-player games. [ABSTRACT FROM AUTHOR]

We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results. [ABSTRACT FROM AUTHOR]

In order to minimize execution times, improve the quality of solutions, and address more extensive target situations, optimization techniques, particularly metaheuristics, are continually improved. Hybridizing procedures are one of these noteworthy strategies due to their wide range of applications. This article describes a hybrid algorithm that combines the k-means method to produce a binary version of the cuckoo search and sine cosine algorithms. The binary algorithms are applied on the NP -hard multi-demand multidimensional knapsack problem. This problem is of particular interest because it has two types of constraints. The first group of constraints is related to the capacity of the knapsacks, and a second type is associated with the demand that must be met. Experiments were undertaken to acquire insight into the contribution of the k-means technique and the local search operator to the final results. Additionally, a comparison is made with two other types of binarization, the first based on a random method and the second based on the percentile concept. The results reveal that the k-means hybrid algorithm consistently provides superior results in most cases studied. In particular, incorporating the local search operator improved the results by an average of 0.23%. On the other hand, when comparing the results with 100 items and 30-30 restrictions, k-means was 1.06% better on average than the random operator. [ABSTRACT FROM AUTHOR]

Purpose: The purpose of this study is to solve NP-Hard drone routing problem for the last-mile distribution. This is suitable for the multi-drones parcel delivery for the various items from a warehouse to many locations. Design/methodology/approach: This study conducts as a mission assignment of the single location per flight with the constraint satisfactions such as various payloads in weight, drone speeds, flight times and coverage distances. A genetic algorithm is modified as the concurrent heuristics approach (GCH), which has the knapsack problem dealing initialization, gene elitism (crossover) and gene replacement (mutation). Those proposed operators can reduce the execution time consuming and enhance the routing assignment of multiple drones. The evaluation value of the routing assignment can be calculated from the chromosome/individual representation by applying the proposed concurrent fitness. Findings: This study optimizes the total traveling time to accomplish the distribution. GCH is flexible and can provide a result according to the first-come-first-served, demanded weight or distance priority. Originality/value: GCH is an alternative option, which differs from conventional vehicle routing researches. Such researches (traveling time optimization) attempt to minimize the total traveling time, distance or the number of vehicles by assuming all vehicles have the same traveling speed; therefore, a specific vehicle assignment to a location is neglected. Moreover, the main drawback is those concepts can lead the repeated selection of best quality vehicles concerning the speed without considering the vehicle fleet size and coverage distance while this study defines the various speeds for the vehicles. Unlike those, the concurrent concept ensures a faster delivery accomplishment by sharing the work load with all participant vehicles concerning to their different capabilities. If the concurrent assignment is applied to the drone delivery effectively, the entire delivery can be accomplished relatively faster than the traveling time optimization. [ABSTRACT FROM AUTHOR]

Nature–inspired computing is a promising field of artificial intelligence. This area is mainly devoted to designing computational models based on natural phenomena to address complex problems. Nature provides a rich source of inspiration for designing smart procedures capable of becoming powerful algorithms. Many of these procedures have been successfully developed to treat optimization problems, with impressive results. Nonetheless, for these algorithms to reach their maximum performance, a proper balance between the intensification and the diversification phases is required. The intensification generates a local solution around the best solution by exploiting a promising region. Diversification is responsible for finding new solutions when the main procedure is trapped in a local region. This procedure is usually carryout by non-deterministic fundamentals that do not necessarily provide the expected results. Here, we encounter the stagnation problem, which describes a scenario where the search for the optimum solution stalls before discovering a globally optimal solution. In this work, we propose an efficient technique for detecting and leaving local optimum regions based on Shannon entropy. This component can measure the uncertainty level of the observations taken from random variables. We employ this principle on three well–known population–based bio–inspired optimization algorithms: particle swarm optimization, bat optimization, and black hole algorithm. The proposal's performance is evidenced by solving twenty of the most challenging instances of the multidimensional knapsack problem. Computational results show that the proposed exploration approach is a legitimate alternative to manage the diversification of solutions since the improved techniques can generate a better distribution of the optimal values found. The best results are with the bat method, where in all instances, the enhanced solver with the Shannon exploration strategy works better than its native version. For the other two bio-inspired algorithms, the proposal operates significantly better in over 70% of instances. [ABSTRACT FROM AUTHOR]

The growing need for profit maximization and cost minimization has made the optimization field very attractive to both researchers and practitioners. In fact, many authors were interested in this field and they have developed a large number of optimization algorithms to solve either academic or real-life problems. Among such algorithms, we cite a well-known metaheuristic called the genetic algorithm. This optimizer tool, as any algorithm, suffers from some drawbacks; like the problem of premature convergence. In this paper, we propose a new selection strategy hoping to avoid such a problem. The proposed selection operator is based on the principle of the k-means clustering method for the purpose of guiding the genetic algorithm to explore different regions of the search space. We have elaborated a genetic algorithm based on this new selection mechanism. We have then tested our algorithm on various data instances of the 0/1 multidimensional knapsack problem. The obtained results are encouraging when compared with those reached by other versions of genetic algorithms and those reached by an adapted version of the particle swarm optimization algorithm. [ABSTRACT FROM AUTHOR]

A New Family of Valid-Inequalities for Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs In "Consistency Cuts for Dantzig-Wolfe Reformulation," Jens Vinther Clausen, Richard Lusby, and Stefan Ropke present a new family of valid inequalities to be applied to Dantzig-Wolfe reformulations with binary linking variables. They show that, for Dantzig-Wolfe reformulations of mixed integer linear programs that satisfy certain properties, it is enough to solve the linear programming relaxation of the Dantzig-Wolfe reformulation with all consistency cuts to obtain integer solutions. An example of this is the temporal knapsack problem; the effectiveness of the cuts is tested on a set of 200 instances of this problem, and the results are state-of-the-art solution times. For problems that do not satisfy these conditions, the cuts can still be used in a branch-and-cut-and-price framework. In order to show this, the cuts are applied to a set of generic mixed linear integer programs from the online library MIPLIB. These tests show the applicability of the cuts in general. This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems. [ABSTRACT FROM AUTHOR]

We consider the problem of recommending relevant content to users of an internet platform in the form of lists of items, called slates. We introduce a variational Bayesian Recurrent Neural Net recommender system that acts on time series of interactions between the internet platform and the user, and which scales to real world industrial situations. The recommender system is tested both online on real users, and on an offline dataset collected from a Norwegian web-based marketplace, FINN.no, that is made public for research. This is one of the first publicly available datasets which includes all the slates that are presented to users as well as which items (if any) in the slates were clicked on. Such a data set allows us to move beyond the common assumption that implicitly assumes that users are considering all possible items at each interaction. Instead we build our likelihood using the items that are actually in the slate, and evaluate the strengths and weaknesses of both approaches theoretically and in experiments. We also introduce a hierarchical prior for the item parameters based on group memberships. Both item parameters and user preferences are learned probabilistically. Furthermore, we combine our model with bandit strategies to ensure learning, and introduce 'in-slate Thompson sampling' which makes use of the slates to maximise explorative opportunities. We show experimentally that explorative recommender strategies perform on par or above their greedy counterparts. Even without making use of exploration to learn more effectively, click rates increase simply because of improved diversity in the recommended slates. [ABSTRACT FROM AUTHOR]

We propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKPs). In particular, we study the solution structure of the problem without the knapsack constraint. In fact an O(n log n) algorithm is suggested in this case. We then use the solution structure to propose an O(n² log n) algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. In the second phase, we solve the Lagrangian dual problem using a traditional single-variable optimization method. We perform a computational test on random instances and compare our algorithm with the general solver CPLEX. [ABSTRACT FROM AUTHOR]

ABC analysis is a commonly used inventory classification technique which consists in splitting a large number of inventory items into three categories, A, B and C: category A consists in the most important items, category B consists in the moderately important items and category C consists in the least important ones. Through this classification, inventory items are managed in an efficient way. In this paper, we argue the benefits of cross-fertilization of both Artificial Intelligence (AI) and MultiCriteria Decision Making (MCDM) techniques to carry out the ABC classification of inventory items. For this purpose, we develop some new hybrid inventory classification models based on metaheuristics (AI techniques) to generate the criteria weights and on Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) method (MCDM technique) to compute the overall weighted score of each item on which the ABC classification is performed. To evaluate the effectiveness of the proposed classification models with respect to some classification models from the literature, a comparative study — based on a service-cost analysis and three real datasets — is conducted. The computational analysis demonstrates that our proposed hybrid models are competitive and produce satisfactory results. The results have also shown, that our proposed models outperform some existing models from the literature. [ABSTRACT FROM AUTHOR]

Population-based approaches have given us new search strategies and ideas in order to solve optimization problems. Usually, these methods are based on the performance carried out by a finite number of agents, which by the interaction between them they evolve and work all over the search space. Also, it is well-known that the correct employment of parameter values in this kind of method can positively impact their performance and behavior. In this context, the present work focuses on the design of a hybrid architecture which smartly balances the population size on run-time. In order to smartly balance and control the population size, a modular approach, named Linear Modular Population Balancer (LMPB), is proposed. The main ideas behind the designed architecture include the solving strategy behind a population-based metaheuristic, the influence of learning components based on multiple statistical modeling methods which transform the dynamic data generated into knowledge, and the possibilities to tackle both discrete and continuous optimization problems. In this regard, three modules are proposed for LMPB, which concern tasks such as the management of the population-based algorithm, parameter setting, probabilities, learning methods, and selection mechanism for the population size to employ. In order to test the viability and effectiveness of our proposed approach, we solve a set of well-known benchmark functions and the multidimensional knapsack problem (MKP). Additionally, we illustrate promising solving results, compare them against state-of-the-art methods which have proved to be good options for solving optimization problems, and give solid arguments for future work in the necessity to keep evolving this type of proposed architecture. [ABSTRACT FROM AUTHOR]

High utility itemsets (HUIs) are items in the dynamically streaming transaction list that generate a high‐profit margin. Many of the real‐time applications depend on finding HUIs from the transaction list. However, HUI mining is time‐consuming and results in high complexity due to memory requirements, a large search space, and the cost of HUI estimation. To overcome these issues we have proposed a novel High Median Utility Itemset Mining (HMUIM) approach. This approach utilizes the HMUI‐Miner which effectively ignores the unnecessary itemsets, that is, items with less profit, and mines the HUIs from the database. Furthermore, it has the limitation of deleting the transaction list based on the sliding window size used while conducting a dynamic streaming dataset. To tackle this issue we proposed a novel Modified Heap‐based Optimizer (MHBO) algorithm which effectively copies the HUIs transaction list and preserves it for further process. The MHBO is the combination of Heap Based Optimizer and nine fuzzy rules. The fuzzy rules are used to analyze the priority of the transaction list and based on that it ignores the transaction list with low priorities. Experimental analysis is performed for the proposed method on the real‐time dataset and compared with HUI and HAUIM approaches. The proposed method reduces the execution time and memory usage based on the minimum threshold. Meanwhile, the proposed MHBO approach is compared with iMEFIM, REX, and FCHUIM state‐of‐art works based on the sliding window concept. The execution time to store the replicated copies of original data is less for our proposed method. [ABSTRACT FROM AUTHOR]

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader's aim is to optimize a linear objective function in the capacity and in the follower's solution, but with respect to different item values. We address a stochastic version of this problem where the follower's profits are uncertain from the leader's perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input, which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader's objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items. Based on this, we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time. [ABSTRACT FROM AUTHOR]

Swarm intelligence heuristic algorithm is used to solve discounted {0-1} knapsack problem (D{0-1} KP). In order to improve the solution efficiency and quality, a repair and optimization strategy is needed to convert abnormal coding individuals into coding individuals that meet the solution constraints. On the basis of introducing the concept of group value density, taking particle swarm optimization algorithm (PSO) as an example, a set of greedy repair and optimization methods based on group (GGROA) is proposed, and the PSO based GGROA for solving D{0-1}KP algorithm (PSO-GGRDKP) is further constructed to explore the feasibility and performance of GGROA. PSO-NGROADKP and PSO-GRDKP are PSO algorithms based on item greedy repair and optimization method. The experimental results on D {0-1} KP standard data set show that compared with PSO-NGROADKP and PSO-GRDKP, PSO-GGRDKP has slightly higher error rate, but the time performance of the algorithm is improved by 13.8% and 12.9% respectively. [ABSTRACT FROM AUTHOR]

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower's problem. More precisely, adopting the robust optimization approach and assuming that the follower's profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower's reaction from the leader's perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader's objective function. [ABSTRACT FROM AUTHOR]

A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem (Rkp) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem (Cbkp). To this end, they started an investigation into its complexity and approximability. The key results are an NP -hardness proof for a more general scenario than Rkp, and a 4.5-approximation for Rkp, raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) Rkp is indeed NP -hard in the considered setting (and even in more restricted settings), and (b) there exists both a pseudopolynomial algorithm and a fully-polynomial time approximation scheme (i.e., efficient approximability within any desired ratio α > 1 ) for Rkp. [ABSTRACT FROM AUTHOR]