Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned ...
详细信息
ISBN:
(纸本)9781728129037
Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned tasks. Spatial crowdsourcing has attracted much attention from both academia and industry. In this paper, we consider a spatial crowdsourcing scenario, where the tasks may have some dependencies among them. Specifically, one task can only be dispatched when its dependent tasks have already been assigned. In fact, task dependencies are quite common in many real-life applications, such as house repairing and holding sports games. We formally define the dependency-aware spatial crowdsourcing (DA-SC), which focuses on finding an optimal worker-and-task assignment under the constraints of dependencies, skills of workers, moving distances and deadlines to maximize the successfully assigned tasks. We prove that the DA-SC problem is NP-hard and thus intractable. Therefore, we propose two approximation algorithms, including a greedy approach and a game-theoretic approach, which can guarantee the approximate bounds of the results in each batch process. Through extensive experiments on both real and synthetic data sets, we demonstrate the efficiency and effectiveness of our DA-SC approaches.
A new class of algorithms for the computation of bilinear forms has been recently introduced [1, 3]. These algorithms approximate the result with an arbitrarily small error. Such approximate algorithms may have a mult...
详细信息
In this paper we describe a heuristic method, based on graph-partitioning algorithms, with the purpose of improving the demarcation of areas for police patrolling. This demarcation seeks to homogenize the number of cr...
详细信息
ISBN:
(纸本)9783540883081
In this paper we describe a heuristic method, based on graph-partitioning algorithms, with the purpose of improving the demarcation of areas for police patrolling. This demarcation seeks to homogenize the number of crimes among the patrol regions. If the map of a particular region is taken as a graph, we can say that the problem faced by police forces (typically preventive police) is similar to the problem of finding balanced connected q partitions of graphs (BCPq). Since this is a problem belonging to the NP-Hard class, approximate algorithms are the most suitable for solving such a problem. The method described in this article obtains results nearest those considered optimal for the more general case of BCPq, for q >= 2.
Edge reliability problem has many applications in different field of science and engineering such as: cognitive science, neuroscience, electrical engineering, network science and so on. The major challenge in this pro...
详细信息
ISBN:
(纸本)9781728150758
Edge reliability problem has many applications in different field of science and engineering such as: cognitive science, neuroscience, electrical engineering, network science and so on. The major challenge in this problem is time complexity of the exact algorithm. Computing the reliability of a network is NP-hard problem. So, computing the reliability of a large scale network is a challenging problem. In this paper, we present a novel algorithm based on a hybrid Monte-Carlo, interpolation and least-square methods to approximate the reliability of a network. The presented algorithm is applied on some networks that the exact reliability polynomial is available for them. the experiments show that the presented algorithm is accurate and robust.
Optical switches are widely considered as the most promising candidate to provide ultra-high speed interconnections. Due to the difficulty in implementing all-optical buffer, optical switches with electronic buffers h...
详细信息
ISBN:
(纸本)9781424499212
Optical switches are widely considered as the most promising candidate to provide ultra-high speed interconnections. Due to the difficulty in implementing all-optical buffer, optical switches with electronic buffers have been proposed recently [1] [4] [5]. Among these switches, the Optical Cut-Through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. In this paper, we consider packet scheduling in this switch with wavelength division multiplexing (WDM). Our goal is to maximize throughput and maintain packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing it to the set packing problem, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of root 2Nk with regard to the number of packets transmitted, where N is the switch size and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing. Based on the approximation algorithm, we also give practical schedulers that can be implemented in fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.
Sketch algorithms are crucial for identifying top-k items in largescale data streams. Existing methods often compromise between performance and accuracy, unable to efficiently handle increasing data volumes with limit...
详细信息
ISBN:
(纸本)9798400704369
Sketch algorithms are crucial for identifying top-k items in largescale data streams. Existing methods often compromise between performance and accuracy, unable to efficiently handle increasing data volumes with limited memory. We present Bubble Sketch, a compact algorithm that excels in both performance and accuracy. Bubble Sketch achieves this by (1) Recording only full keys of hot items, significantly reducing memory usage, and (2) Using threshold relocation to resolve conflicts, enhancing detection accuracy. Unlike traditional methods, Bubble Sketch eliminates the need for a MinHeap, ensuring fast processing speeds. Experiments show Bubble Sketch outperforms the other seven algorithms compared, with the highest throughput and precision, and surpasses HeavyKeeper in accuracy by up to two orders of magnitude.
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streamin...
详细信息
ISBN:
(纸本)9781728125831
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.
Big data clustering is a fundamental problem with a vast number of applications. Due to the increasing size of data, interests in clustering problems in distributed computation models have increased. On the other hand...
详细信息
ISBN:
(纸本)9783030967727;9783030967710
Big data clustering is a fundamental problem with a vast number of applications. Due to the increasing size of data, interests in clustering problems in distributed computation models have increased. On the other hand, because important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new distributed algorithms for the fair k-center problem with outliers. Our main contributions are: (1) In the fair k-center problem with outliers setting we give a 4-approximation ratio algorithm. (2) In the distributed fair k-center problem with outliers setting we give a 18-approximation ratio algorithm.
Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal p...
详细信息
ISBN:
(数字)9781665408837
ISBN:
(纸本)9781665408837
Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present (epsilon, delta)-approximate MaxRST query, which returns an approximate answer having the relative error epsilon to the optimal covered weight with probability at least delta. Furthermore, two complementary sampling-based (epsilon, delta)-approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.
We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple ...
详细信息
ISBN:
(纸本)9780769544762
We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple polygonalizations of a fixed point set and finds the minimum area polygon, in O(n(3)) time and using O(n(2)) memory.
暂无评论