Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimizing the Maximum Interference is Hard
730
0
0.0
(
0
)
Added by
Kevin Buchin
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Authors
Kevin Buchin
Ask ChatGPT about the research
No Arabic abstract
We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.
rate research
Read More
202 -
Adrien Friggeri
, Eric Fleury (ENS / LIPn Laboratoire de lInformatique du Parallelisme / INRIA Grenoblen Rh^one-Alpes
2011
We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. In particular, it has been shown that there exists an inherent tradeoff between update consistency and speed. This paper revisits the problem of updating an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (greedy) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.
In this short paper, we consider the problem of designing a near-optimal competitive scheduling policy for $N$ mobile users, to maximize the freshness of available information uniformly across all users. Prompted by the unreliability and non-stationarity of the emerging 5G-mmWave channels for high-speed users, we forego of any statistical assumptions of the wireless channels and user-mobility. Instead, we allow the channel states and the mobility patterns to be dictated by an omniscient adversary. It is not difficult to see that no competitive scheduling policy can exist for the corresponding throughput-maximization problem in this adversarial model. Surprisingly, we show that there exists a simple online distributed scheduling policy with a finite competitive ratio for maximizing the freshness of information in this adversarial model. Moreover, we also prove that the proposed policy is competitively optimal up to an $O(ln N)$ factor.
The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common model is the receiver-centric, in which the interference of a node $p$ is defined as the number of other nodes whose transmission range covers $p$. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in $O(n^3)$ time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.
We prove a version of Jonsson-Mustac{t}v{a}s Conjecture, which says for any graded sequence of ideals, there exists a quasi-monomial valuation computing its log canonical threshold. As a corollary, we confirm Chi Lis conjecture that a minimizer of the normalized volume function is always quasi-monomial. Applying our techniques to a family of klt singularities, we show that the volume of klt singularities is a constructible function. As a corollary, we prove that in a family of klt log Fano pairs, the K-semistable ones form a Zariski open set. Together with [Jia17], we conclude that all K-semistable klt Fano varieties with a fixed dimension and volume are parametrized by an Artin stack of finite type, which then admits a separated good moduli space by [BX18, ABHLX19], whose geometric points parametrize K-polystable klt Fano varieties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
