An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate within one wireless hop. In the recent years, cognit...
详细信息
ISBN:
(纸本)9780769543642
An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate within one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A CR transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A CR node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a CR network. In this paper, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions.
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present...
详细信息
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm ***,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.
In dealing with abrasive waterjet machining（AWJM） simulation,most literatures apply finite element method（FEM） to build pure waterjet models or single abrasive particle erosion *** overcome the mesh distortion cau...
详细信息
In dealing with abrasive waterjet machining（AWJM） simulation,most literatures apply finite element method（FEM） to build pure waterjet models or single abrasive particle erosion *** overcome the mesh distortion caused by large deformation using FEM and to consider the effects of both water and abrasive,the smoothed particle hydrodynamics（SPH） coupled FEM modeling for AWJM simulation is presented,in which the abrasive waterjet is modeled by SPH particles and the target material is modeled by *** two parts interact through contact *** this model,abrasive waterjet with high velocity penetrating the target materials is simulated and the mechanism of erosion is *** relationships between the depth of penetration and jet parameters,including water pressure and traverse speed,etc,are analyzed based on the *** simulation results agree well with the existed experimental *** mixing multi-materials SPH particles,which contain abrasive and water,are adopted by means of the randomized algorithm and material model for the abrasive is *** study will not only provide a new powerful tool for the simulation of abrasive waterjet machining,but also be beneficial to understand its cutting mechanism and optimize the operating parameters.
We study optimal solutions to an abstract optimization problem for measures, which is a generalization of classical variational problems in information theory and statistical physics. In the classical problems, inform...
详细信息
We study optimal solutions to an abstract optimization problem for measures, which is a generalization of classical variational problems in information theory and statistical physics. In the classical problems, information and relative entropy are defined using the Kullback-Leibler divergence, and for this reason optimal measures belong to a one-parameter exponential family. Measures within such a family have the property of mutual absolute continuity. Here we show that this property characterizes other families of optimal positive measures if a functional representing information has a strictly convex dual. Mutual absolute continuity of optimal probability measures allows us to strictly separate deterministic and non-deterministic Markov transition kernels, which play an important role in theories of decisions, estimation, control, communication and computation. We show that deterministic transitions are strictly sub-optimal, unless information resource with a strictly convex dual is unconstrained. For illustration, we construct an example where, unlike non-deterministic, any deterministic kernel either has negatively infinite expected utility (unbounded expected error) or communicates infinite information.
Multi-dimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging multidimensional problems of nonstationary optimization, it is suggested to...
详细信息
Multi-dimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging multidimensional problems of nonstationary optimization, it is suggested to use a stochastic approximation algorithm (like SPSA) with perturbed input and constant step-size which has simple form. We get a finite bound of residual between estimates and time-varying unknown parameters when observations are made under an unknown but bounded noise. Applications of the algorithm are considered for a random walk, an optimization of UAV's flight, and a load balancing problem.
An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 = 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given g...
详细信息
An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.
Keys and locks are an omnipresent fixture in our daily life, limiting physical access to privileged resources or spaces. While most of us may have marveled at the intricate shape of a key, the usually hidden mechanica...
详细信息
Keys and locks are an omnipresent fixture in our daily life, limiting physical access to privileged resources or spaces. While most of us may have marveled at the intricate shape of a key, the usually hidden mechanical complexity within a cylinder lock is even more awe-inspiring, containing a multitude of tiny movable parts such as springs and pins that have been precision-manufactured from highly customized materials using specialized fabrication techniques. It is perhaps unknown that mechanical cylinder locks possess a number of important design constraints that uniquely distinguish them from their electronic counterparts. Aside from manufacturing costs, a cylinder's most significant limitations are the upper bound on its outer dimensions as well as the lower bound on the size of its internal mechanical security features (pins). Cylinders cannot be very large so that they still fit into doors and avoid the need for large keys. Pins cannot be too small in order to withstand wear and tear and provide appropriate physical security. Even more complex than a single cylinder is the design of an ensemble of "related" locks as may occur in an apartment, office building, factory, or hospital, for example. Instead of controlling access to one resource, the set of open/not open relationships between all the keys and locks of such a lock system may encode a complex and diverse hierarchy of privileges for each individual key, from the benign opening of the front entrance by all staff to heavily restricted access to confidential documents or hazardous materials by selected personnel only. For the mathematician or computer scientist, lock system design poses a fascinating array of theoretical and computational challenges. Abstraction via an algebraic model shows that cylinders and keys of a lock system can be represented within an upper semilattice, where the induced partial ordering establishes the must open/must not open functions. Finding an "equivalent" sub-semilattice withi
Given a digraph D=(V,A) and a set of kappa pairs of vertices in V, we are interested in finding, for each pair (x(i),y(i)), a directed path connecting x(i) to y(i) such that the set of kappa paths so found is arc-disj...
详细信息
Given a digraph D=(V,A) and a set of kappa pairs of vertices in V, we are interested in finding, for each pair (x(i),y(i)), a directed path connecting x(i) to y(i) such that the set of kappa paths so found is arc-disjoint. For arbitrary graphs the problem is NP-complete, even for kappa=2. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and the degree r is sufficiently large, then all sets of kappa=Omega (n/log n) pairs of vertices can be joined. This is within a constant factor of best possible.
We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a...
详细信息
We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a channel to its ith neighbor (modulo degree) on that list, beginning from a randomly chosen starting position. Then, the channels can be used for bi-directional communication in that step. The goal is to spread a message efficiently to all nodes of the graph. For random graphs (with sufficiently many edges) we present an address-oblivious algorithm with runtime O(logn) that uses at most O(nloglogn) message transmissions. For hypercubes of dimension logn we present an address-oblivious algorithm with runtime O(logn) that uses at most O(n(loglogn)(2)) message transmissions. Together with a result of Elsasser (Proc. of SPAA'06, pp. 148-157, 2006), our results imply that for random graphs the communication complexity of the quasirandom phone call model is significantly smaller than that of the standard phone call model.
A new algorithm is presented which provides a fast method for the computation of recently developed Fourier continuations (a particular type of Fourier extension method) that yield superalgebraically convergent Fourie...
详细信息
A new algorithm is presented which provides a fast method for the computation of recently developed Fourier continuations (a particular type of Fourier extension method) that yield superalgebraically convergent Fourier series approximations of nonperiodic functions. Previously, the coefficients of an approximating Fourier series have been obtained by means of a regularized singular value decomposition (SVD)-based least-squares solution to an overdetermined linear system of equations. These SVD methods are effective when the size of the system does not become too large, but they quickly become unwieldy as the number of unknowns in the system grows. We demonstrate a novel decoupling of the least-squares problem which results in two systems of equations, one of which may be solved quickly by means of fast Fourier transforms (FFTs) and another that is demonstrated to be well approximated by a low-rank system. Utilizing randomized algorithms, the low-rank system is reduced to a significantly smaller system of equations. This new system is then efficiently solved with drastically reduced computational cost and memory requirements while still benefiting from the advantages of using a regularized SVD. The computational cost of the new algorithm in on the order of the cost of a single FFT multiplied by a slowly increasing factor that grows only logarithmically with the size of the system.
暂无评论