In this paper we ask whether approximation for abstract argumentation is useful in practice, and in particular whether reasoning with grounded semantics - which has polynomial runtime - is already an approximation app...
详细信息
In this paper we ask whether approximation for abstract argumentation is useful in practice, and in particular whether reasoning with grounded semantics - which has polynomial runtime - is already an approximation approach sufficient for several practical purposes. While it is clear from theoretical results that reasoning with grounded semantics is different from, for example, skeptical reasoning with preferred semantics, we investigate how significant this difference is in actual argumentation frameworks. As it turns out, in many graphs models, reasoning with grounded semantics actually approximates reasoning with other semantics almost perfectly. An algorithm for grounded reasoning is thus a conceptually simple approximation algorithm that not only does not need a learning phase - like recent approaches - but also approximates well - in practice - several decision problems associated to other semantics.
Route-oriented participants recruitment is a critical problem in collaborative crowdsensing, where task publisher uses monetary reward to motivate private cars collecting data along their routes. For map producers, ro...
详细信息
ISBN:
(纸本)9783030009168;9783030009151
Route-oriented participants recruitment is a critical problem in collaborative crowdsensing, where task publisher uses monetary reward to motivate private cars collecting data along their routes. For map producers, route-oriented crowdsensing scheme helps them achieve maximum roads coverage with a limited budget, by selecting appropriate participants from a group of candidates. Focused on route-oriented participants recruitment problem, this paper first formalizes the road network and vehicle route model. Each vehicle's route is mapped to a coverage rate on the road set. The recruitment problem therefore transforms to a combinatorial optimization problem, which has proved to be NP-hard. To find a solution, we proposed an approximation algorithm, which leverages submodularity to reduce computation complexity and has a worst performance guarantee. Finally we evaluate the performance of proposed algorithm on real road and trajectory data in Beijing, China.
作者：
杨盛吴澄CIMS-ERC
Tsinghua University Beijing 100084
This paper models the scheduling of one type of flexible transfer line as an integer programming *** the integer program falls within the NP class of problems, then its complexity increases exponentially as theproblem...
详细信息
This paper models the scheduling of one type of flexible transfer line as an integer programming *** the integer program falls within the NP class of problems, then its complexity increases exponentially as theproblem size increases, making the problem intractable even for a medium size system. An approximate algorithm,whose complexity only increases algebraically with the problem size, is presented to obtain suboptimal solutions ofscheduling problems. Numerical experiments indicate that the suboptimal solution is near to the optimal solution inthe general case where the neighboring points are dense around the optimal solution in the feasible ration of the integer program.
Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a verte...
详细信息
ISBN:
(纸本)9781450369763
Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a vertex r is an element of V (G), we present a novel adaptive algorithm for estimating betweenness score of r. Our algorithm first computes two subsets of the vertex set of G, called RF(r) and RT(r). They define the sample spaces of the start-points and the end-points of the samples. Then, it adaptively samples from RF(r) and RT(r) and stops as soon as some condition is satisfied. The stopping condition depends on the samples met so far, vertical bar RF(r)vertical bar and vertical bar RT(r)vertical bar. We show that compared to the well-known existing algorithms, our algorithm gives a better (lambda, delta)-approximation. Then, we propose a novel algorithm for estimating k-path centrality of r. Our algorithm is based on computing two sets RF(r) and D(r). While RF(r) defines the sample space of the source vertices of the sampled paths, D(r) defines the sample space of the other vertices of the paths. We show that in order to give a (lambda, delta)-approximation of the k-path score of r, our algorithm requires considerably less samples. Moreover, it processes each sample faster and with less memory. Finally, we empirically evaluate our proposed algorithms and show their superior performance. Also, we show that they can be used to efficiently compute centrality scores of a set of vertices.
Multiobjectives linear programming (MOLP) is one of the most important models for decision-making experts. When the parameters can be represented by fuzzy numbers, it would be more interesting. In this paper, we prese...
详细信息
ISBN:
(纸本)9780819490261
Multiobjectives linear programming (MOLP) is one of the most important models for decision-making experts. When the parameters can be represented by fuzzy numbers, it would be more interesting. In this paper, we present an approximate algorithm for solving the fuzzy multiobjectives linear programming (FMOLP), where the coefficients of objective functions and constraints are fuzzy. This algorithm solved MOLP problem obtained after converting fuzzy coefficients to fixed coefficients, by using the maximin method. A detailed description and analysis of the algorithm are supplied, and an illustrative example is presented.
An efficient discovery algorithm of frequently occurring patterns, called motifs, in a time series would be useful as a tool for summarizing and visualizing big time series databases. In this paper, we propose an effi...
详细信息
An efficient discovery algorithm of frequently occurring patterns, called motifs, in a time series would be useful as a tool for summarizing and visualizing big time series databases. In this paper, we propose an efficient approximate algorithm, called DiscMotifs, to discover the K most significant (Kk/S) motifs from time series. First, the proposed algorithm transforms the time series into a SAX representation and then the algorithm divides the SAX representation into subsequences. Next, these subsequences are linearized by projecting them into a one-dimensional space based on their distances form a randomly selected reference point, or a subsequence. By utilizing the linear ordering of subsequences, DiscMotifs efficiently discovers the KMS motifs. DiscMotifs algorithm requires a storage space linear to the number of subsequences. We demonstrate the feasibility of this approach on several synthetic and real application datasets. (C) 2020 The Authors. Published by Elsevier B.V.
There are growing interests in algorithms over data streams recently. This paper introduces the problem of sampling from sliding windows of recent data items from data streams and presents two random sampling algorith...
详细信息
ISBN:
(纸本)9812565329
There are growing interests in algorithms over data streams recently. This paper introduces the problem of sampling from sliding windows of recent data items from data streams and presents two random sampling algorithms for this problem. The first algorithm is a basic window-based sampling algorithm (BWRS algorithm) for count-based sliding window. BWRS algorithm extends classic reservoir sampling to deal with the expiration of data elements from count-based sliding window, and can avoid drawbacks of classic reservoir sampling. The second algorithm is a stratified multistage sampling algorithm for time-based sliding window (SMS algorithm). The SMS algorithm takes different sampling fraction in different strata from time-based sliding window, and works even when the number of data items in the sliding window varies dynamically over time. The theoretic analysis and experiments show that the algorithms are effective and efficient for continuous data streams processing.
One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no co...
详细信息
ISBN:
(纸本)9781538650356
One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no comprehensive and in-depth analysis and comparison of these algorithms in the literature. In this paper, we first present a generic algorithm that is used to express different approximate algorithms in terms of probability distributions. Using this generic algorithm, we show that interestingly existing methods have the same theoretical accuracy. Then, we present an extension of distance-based sampling to group betweenness centrality, which is based on a new notion of distance between a single vertex and a set of vertices. In the end, to empirically evaluate efficiency and accuracy of different algorithms, we perform experiments over several real-world networks. Our extensive experiments reveal that those approximate algorithms that are based on shortest path sampling are orders of magnitude faster than those algorithms that are based on pair sampling, while these two types of algorithms have almost comparable empirical accuracy.
Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n2) worst-case running time, an expected-complexity analysis shows that, under reasonable probabil...
详细信息
In this paper we present four new algorithms for solving Minimum Base Problem (MBP) which is known to be NP-complete. The problem arises in wide or dense sensor networks in which a huge number of sensors provides a hi...
详细信息
ISBN:
(纸本)9781665426053
In this paper we present four new algorithms for solving Minimum Base Problem (MBP) which is known to be NP-complete. The problem arises in wide or dense sensor networks in which a huge number of sensors provides a highly redundant source of information and should be reduced for further processing. In many cases a proper selection of nonredundant subset of the set of all sensors is reasonable both from economical point of view and the computational complexity of processing vast input data by software or hardware. Both exact and approximate algorithms are to be developed and applied for this task. In addition a hybrid metaheuristic shown.
暂无评论