We introduce a randomized approximation algorithm for NP-hard problem of finding a subset of m vectors chosen from n given vectors in multidimensional Euclidean space R-k such that the norm of the corresponding sum-ve...
详细信息
ISBN:
(纸本)9783319449142;9783319449135
We introduce a randomized approximation algorithm for NP-hard problem of finding a subset of m vectors chosen from n given vectors in multidimensional Euclidean space R-k such that the norm of the corresponding sum-vector is maximum. We derive the relation between algorithm's time complexity, relative error and failure probability parameters. We show that the algorithm implements Polynomial-time randomized Approximation Scheme (PRAS) for the general case of the problem. Choosing particular parameters of the algorithm one can obtain asymptotically exact algorithm with significantly lower time complexity compared to known exact algorithm. Another set of parameters provides polynomial-time 1/2-approximation algorithm for the problem. We also show that the algorithm is applicable for the related (minimization) clustering problem allowing to obtain better performance guarantees than existing algorithms.
The problem of small UAVs flight optimization is considered. To solve this problem thermal updrafts are used. For the precise detection of the thermal updrafts center the simultaneous perturbation stochastic approxima...
详细信息
The problem of small UAVs flight optimization is considered. To solve this problem thermal updrafts are used. For the precise detection of the thermal updrafts center the simultaneous perturbation stochastic approximation (SPSA) type algorithm is proposed. If UAVs use thermal updrafts so they can save the energy during the flight. Therefore the flight time will be vary for different UAVs. In order to optimize the area monitoring, the consensus approach has been proposed.
In this paper, we investigate the problem of optimal road side units (RSUs) placement in Vehicular Ad Hoc Network (VANET) on a highway, which enables the VANET maintain a good connectivity. Our goal is to find out min...
详细信息
ISBN:
(纸本)9780769551593
In this paper, we investigate the problem of optimal road side units (RSUs) placement in Vehicular Ad Hoc Network (VANET) on a highway, which enables the VANET maintain a good connectivity. Our goal is to find out minimal number of road side units, such that the vehicles could communicate with RSUs. These road side units are connected by wire. We develop a randomized algorithm to deploy road side units in the VANET. It gives an approximation to the optimal distance to guarantee the information can be passed to RSUs from the accident site via the VANET. Simulations are conducted to show the performance of our proposed method.
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time O(m root log n center dot log log n) in the comparison-addit...
详细信息
ISBN:
(纸本)9798350318944
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time O(m root log n center dot log log n) in the comparison-addition model. This is the first algorithm to break the O(m + n log n) time bound for real-weighted sparse graphs by Dijkstra's algorithm with Fibonacci heaps. Previous undirected non-negative SSSP algorithms give time bound of O(m alpha(m, n) + min{n log n, n log log r}) in comparison-addition model, where a is the inverse-Ackermann function and r is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of Omega(m + min{n log n, n log log r}) for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchy-based approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.
Square root extraction plays a key role in cryptosystems based on elliptic curves. Motwani and Raghavan had proposed an algorithm for square root extraction over finite field F-p, where p is an odd prime. It is a rand...
详细信息
ISBN:
(纸本)9783642537035;9783642537028
Square root extraction plays a key role in cryptosystems based on elliptic curves. Motwani and Raghavan had proposed an algorithm for square root extraction over finite field F-p, where p is an odd prime. It is a randomized algorithm with expected running time O(len(p)(4)). Its complexity relies mainly on the loops calling Euclid's algorithm for polynomials over F-p. In this paper, we propose an improvement of it. The new algorithm calls a subroutine for computing a Legendre symbol. Since the running time of computing a Legendre symbol is much less than that of Euclid's algorithm for polynomials over F-p, the new algorithm is more efficient. It only takes time O(len(p)(3)). We also compare the new algorithm with those algorithms for square root extraction over finite fields.
With the application of multimedia information, a large amount of video information comes forth, how to retrieval the information required from the vast amount of data is vital. Content-based Video Retrieval is one of...
详细信息
ISBN:
(纸本)9781424473854
With the application of multimedia information, a large amount of video information comes forth, how to retrieval the information required from the vast amount of data is vital. Content-based Video Retrieval is one of the leading methods to get the needed information from the vast amount of video data. Technology to extract key frames, which is an important part of content-based video retrieval, was studied carefully. In the compressed domain environment, firstly divide the two frames to be compared into sub-blocks, and then use randomized algorithm to select a subset of the divided sub-blocks to calculate similarity, and then to select key frames. The method can be guaranteed to meet the inter-frame similarity calculation under a certain precision, significantly reducing the number of sub-blocks needed to compare, thereby enhancing operational efficiency of the algorithm, and experimental results proved to be better.
The detection performance of active sonar is often hindered by the presence of seabed reverberation in shallow water. Separating the reverberations from the target echo and noise in the received signal is a crucial ch...
详细信息
The detection performance of active sonar is often hindered by the presence of seabed reverberation in shallow water. Separating the reverberations from the target echo and noise in the received signal is a crucial challenge in the field of underwater acoustic signal processing. To address this issue, an improved Go-SOR decomposition method is proposed based on the subspace-orbit-randomized singular value decomposition (SOR-SVD). This method successfully extracts the low-rank structure with a certain striation pattern. The results demonstrate that the proposed algorithm outperforms both the original Go algorithm and the current state-of-the-art (SOTA) algorithm in terms of the definition index of the low-rank structure and computational efficiency. Based on the monostatic reverberation theory of the normal mode, it is established that the low-rank structure is consistent with the low-frequency reverberation interference striation. This study examines the interference characteristics of the low-rank structure in the experimental sea area and suggests that the interferences of the fifth and seventh modes mainly control the low-rank structure. The findings of this study can be applied to seafloor exploration, reverberation waveguide invariant (RWI) extraction, and data-driven reverberation suppression methods.
Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of ...
详细信息
Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k(2)+1/2k(2)+1 -approximation for k >= 3. We also give a randomized root 17-3/ -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and Zivny [ACM Trans. algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities.
Far a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visi...
详细信息
Far a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P's vertices that is contained in P.
The k-means clustering is one of the most popular schemes to solve the problem of clustering. This paper investigates the approximate algorithm for the k-means clustering by means of selecting the k initial points use...
详细信息
ISBN:
(纸本)9781424421138
The k-means clustering is one of the most popular schemes to solve the problem of clustering. This paper investigates the approximate algorithm for the k-means clustering by means of selecting the k initial points used as centers from the original point set. It is proved that an expected 2-approximation factor can be obtained, if k centers belong to one of the optimal sub cluster points respectively. To find these k points, a randomized algorithm is proposed which obtain an expected 2-approximation factor with high probability. This algorithm selects some points from the original points to be used as candidate centers, and the size of the sample is based on having at least points of each cluster. At last, some-examples are selected to verify our algorithm and get good results.
暂无评论