اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWeb of Lossy Adapters for Interface Interoperability: An Algorithm and NP-completeness of Minimization
232
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
By using different interface adapters for different methods, it is possible to construct a maximally covering web of interface adapters which incurs minimum loss during interface adaptation. We introduce a polynomial-time algorithm that can achieve this. However, we also show that minimizing the number of adapters included in a maximally covering web of interface adapters is an NP-complete problem.
قيم البحث
اقرأ أيضاً
Despite providing similar functionality, multiple network services may require the use of different interfaces to access the functionality, and this problem will only get worse with the widespread deployment of ubiquitous computing environments. One
way around this problem is to use interface adapters that adapt one interface into another. Chaining these adapters allows flexible interface adaptation with fewer adapters, but the loss incurred due to imperfect interface adaptation must be considered. This paper outlines a mathematical basis for analyzing the chaining of lossy interface adapters. We also show that the problem of finding an optimal interface adapter chain is NP-complete.
We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G(V,E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay probl
em. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log (Nd_{max}) (N^5d_{max}^{2.5})(log R+N^2d_{max}log(N^2d_{max}))), where N = max{|V|,|E|} and d_{max} is the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.
The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed t
o be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P=NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.
Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set o
f all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years.
A boundary evolution Algorithm (BEA) is proposed by simultaneously taking into account the bottom and the high-level crossover and mutation, ie., the boundary of the hierarchical genetic algorithm. Operators and optimal individuals based on optional annealing are designed. Based on the numerou
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
