SciCombinator

Discover the most talked about and latest scientific content & concepts.

Concept: Knapsack problem

305

The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.

Concepts: Mathematics, Quantum computer, Computer, Computation, Problem solving, Computational complexity theory, Elementary mathematics, Knapsack problem

0

The Internet of Things (IoT) is a vision of the upcoming society. It can provide pervasive communication between two or more entities using 4G-LTE (Long Term Evolution) communication technology. In 4G-LTE networks, there are two important problems: helping manage the spectrum demands of IoT devices and achieving much more revenue with the limited resource. This paper proposes a pricing framework to investigate the spectrum leasing in mobile heterogeneous networks with single macrocell and multiple femtocells. We modeled the leasing procedure between the macrocell service provider (MSP) and femtocell holders (FHs) as an auction to motivate the MSP to lease its spectrum resource. All FHs act as the bidders, and the monopolist MSP acts as the auctioneer. In the auction, FHs submit their bids to rent the spectrum resource so that they can make a profit by selling it to their subscribers. The MSP determines the spectrum leasing amount and chooses the winning FHs by solving the dynamic programming-based 0-1 knapsack problem. In our proposed framework, we focus on the spectrum pricing strategy and revenue maximization of the MSP. The simulation results show that the proposed scheme provides effective motivation for the MSP to lease the spectrum to FHs, and both the MSP and FHs can benefit from spectrum leasing.

Concepts: GSM, Renting, Knapsack problem, Continuous knapsack problem, Profit maximization, Femtocell, Macrocell

0

P systems are computing models inspired by some basic features of biological membranes. In this work, membrane division, which provides a way to obtain an exponential workspace in linear time, is introduced into (cell-like) P systems with communication (symport/antiport) rules, where objects are never modified but they just change their places. The computational efficiency of this kind of P systems is studied. Specifically, we present a (uniform) linear time solution to the NP-complete problem, Subset Sum by using division rules for elementary membranes and communication rules of length at most 3. We further prove that such P system allowing division rules for non-elementary membranes can efficiently solve the PSPACE-complete problem, QSAT, in a uniform way.

Concepts: Mathematics, Cell membrane, Problem solving, Computational complexity theory, NP-complete, Boolean satisfiability problem, Knapsack problem, Complexity class

0

The maximum cut (MAX-CUT) problem is to find a bipartition of the vertices in a given graph such that the number of edges with ends in different sets reaches the largest. Though, several experimental investigations have shown that evolutionary algorithms (EAs) are efficient for this NP-complete problem, there is little theoretical work about EAs on the problem. In this paper, we theoretically investigate the performance of EAs on the MAX-CUT problem. We find that both the (1+1) EA and the (1+1) EA*, two simple EAs, efficiently achieve approximation solutions of (m/2)+(¼)s(G) and (m/2)+(½)(√8m+1-1), where m and s(G) are respectively the number of edges and the number of odd degree vertices in the input graph. We also reveal that for a given integer k the (1+1) EA* finds a cut of size at least k in expected runtime O(nm+1/δ´k) and a cut of size at least (m/2)+k in expected runtime O(n²m+1/δ(¶´/³)k²), where δ is a constant mutation probability and n is the number of vertices in the input graph. Finally, we show that the (1+1) EA and the (1+1) EA* are better than some local search algorithms in one instance, and we also show that these two simple EAs may not be efficient in another instance.

Concepts: Algorithm, Evolution, Computational complexity theory, Combinatorial optimization, NP-complete, Knapsack problem, NP-complete problems, Karp's 21 NP-complete problems

0

Abstract We describe a novel Hyper-heuristic system which continuously learns over time to solve a combinatorial optimisation problem. The system continuously generates new heuristics and samples problems from its environment; representative problems and heuristics are incorporated into a self-sustaining network of interacting entities inspired by methods in Artificial Immune Systems.The network is plastic in both its structure and content leading to the following properties: it exploits existing knowledge captured in the network to rapidly produce solutions; it can adapt to new problems with widely differing characteristics; it is capable of generalising over the problem space. The system is tested on a large corpus of 3968 new instances of 1D-bin packing problems as well as on 1370 existing problems from the literature; it shows excellent performance in terms of the quality of solutions obtained across the datasets and in adapting to dynamically changing sets of problem instances compared to previous approaches. As the network self-adapts to sustain a minimal repertoire of both problems and heuristics that form a representative map of the problem space, the system is further shown to be computationally efficient and therefore scalable.

Concepts: Mathematics, Learning, Knowledge, Problem solving, Computational complexity theory, Adaptation, Combinatorial optimization, Knapsack problem

0

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.

Concepts: Time, Algorithm, Space, Programming language, Optimization, Computational complexity theory, Dynamic programming, Knapsack problem

0

In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared to exact algorithms in terms of runtime and quality metrics. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.

Concepts: Algorithm, Computational complexity theory, Combinatorial optimization, Knapsack problem, Continuous knapsack problem