检索结果-内蒙古大学图书馆

37th annual acm symposium on Applied Computing

作者： Chang, Duhyeuk Lee, Jungsoo Jeong, Byunghyun Heo, Junyoung Hansung Univ Seoul South Korea

ISBN: (纸本)9781450387132

through this study, we intend to improve the utilization of hyperspectral high-capacity data feature information by reducing the dimension of neural network inputs in embedded systems. through the number of bands clustered into subsets due to differences in maximum and minimum values for each band, the unique number of band selections and bands are determined for each data set by applying band selection algorithms in each subset. Unlike RGB images, hyperspectral images are used to identify objects collected as information on an electromagnetic spectrum, It is used for exploration of objects or materials because it has more information than general images. A band selection technique is used to reduce the amount of information on the hyperspectral image to be processed. Existing band selection techniques are statistics-based heuristic techniques[3, 8] that take a long time and often lack generality and universality. To compensate for this, in this paper, representative bands for each data set are selected and used for band selection through discrete Range among quantization concepts. through the experimental results, the proposed technique showed that the execution time was much faster than the existing band selection method, and the performance accuracy was similar to that of the original, even though the number of bands was reduced from 1/7 to 1/10.

关键词： Band selection Hyperspectral imaging Pixel classification Pooling operation

来源：评论

学校读者我要写书评

暂无评论

SIMPLE, DETERMINISTIC, CONSTANT-ROUND COLORING IN CONGESTED CLIQUE AND MPC

引用

siam JOURNAL ON COMPUTING 2021年第5期50卷 1603-1626页

作者： Czumaj, Artur Davies, Peter Parter, Merav Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat Coventry CV4 7AL W Midlands England IST Austria A-3400 Klosterneuburg Austria Weizmann Inst Sci IL-7610001 Rehovot Israel

We settle the complexity of the ( increment +1)-coloring and ( increment +1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. this matches the complexity of the recent breakthrough randomized constant-round ( increment + 1)-list coloring algorithm due to Chang et al. [Proceedings of the 38th acm symposium on Principles of Distributed Computing, 2019] and significantly improves upon the state-of-the-art O (log increment )-round deterministic ( increment + 1)-coloring bound of Parter [Proceedings of the 45th annual International Colloquium on Automata, Languages and Programming]. A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, and Pettie [Proceedings of the 50th annual acm SIGACT symposium on theory of Computing, 2018], our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O (1) recursion steps, the remaining uncolored subgraph within each bin has linear size and thus can be solved locally by collecting it to a single node. this algorithm can also be implemented in the massively parallel computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime, in which machines have sublinear space: we present the first deterministic ( increment + 1)-list coloring algorithm designed for sublinear-space MPC, which runs in O (log increment + log log n) rounds.

关键词： congested clique massively parallel computation coloring derandomization

来源：评论

学校读者我要写书评

暂无评论

Normalizers and permutational isomorphisms in simply-exponential time 31

Normalizers and permutational isomorphisms in simply-exponen...

引用

31st annual acm-siam symposium on discrete algorithms (SODA)

作者： Wiebking, Daniel Rhein Westfal TH Aachen Aachen Germany

We show that normalizers and permutational isomorphisms of permutation groups given by generating sets can be computed in time simply exponential in the degree of the groups. the result is obtained by exploiting canon... 详细信息

ISBN: (纸本)9781611975994

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

the Complexity of Contracts 31

The Complexity of Contracts

引用

31st annual acm-siam symposium on discrete algorithms (SODA)

作者： Dutting, Paul Roughgarden, Tim Cohen, Inbal-Talgam London Sch Econ Dept Math Houghton St London WC2A 2AE England Columbia Univ Dept Comp Sci 500 West 120th St New York NY 10027 USA Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

ISBN: (纸本)9781611975994

We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing the principal's expected payoff over all incentive-compatible contracts known in economics as "second-best" solutions. We also study a natural relaxation to approximately incentive-compatible contracts. We focus on principal-agent settings with succinctly described (and exponentially large) outcome spaces. We show that the computational complexity of computing a near-optimal contract depends fundamentally on the number of agent actions. For settings with a constant number of actions, we present a fully polynomial-time approximation scheme (FPTAS) for the separation oracle of the dual of the problem of minimizing the principal's payment to the agent, and use this subroutine to efficiently compute a delta-incentivecompatible (delta-IC) contract whose expected payoff matches or surpasses that of the optimal IC contract. With an arbitrary number of actions, we prove that the problem is hard to approximate within any constant c. this inapproximability result holds even for delta-IC contracts where delta is a sufficiently rapidly-decaying function of c. On the positive side, we show that simple linear delta-IC contracts with constant delta are sufficient to achieve a constant-factor approximation of the "first-best" (full-welfare-extracting) solution, and that such a contract can be computed in polynomial time.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Cake Cutting on Graphs: A discrete and Bounded Proportional Protocol 31

Cake Cutting on Graphs: A Discrete and Bounded Proportional ...

引用

31st annual acm-siam symposium on discrete algorithms (SODA)

作者： Bei, Xiaohui Sun, Xiaoming Wu, Hao Zhang, Jialin Zhang, Zhijie Zi, Wei Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Chinese Acad Sci Univ Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9781611975994

the classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols [16]. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graph. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envy-free protocol given in [5].

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Communication Complexity of discrete Fair Division 30

Communication Complexity of Discrete Fair Division

引用

30th annual acm-siam symposium on discrete algorithms (SODA)

作者： Plaut, Benjamin Roughgarden, Tim Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781611975482

We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Zeros of Holant problems: locations and algorithms 30

Zeros of Holant problems: locations and algorithms

引用

30th annual acm-siam symposium on discrete algorithms (SODA)

作者： Guo, Heng Liao, Chao Lu, Pinyan Zhang, Chihao Univ Edinburgh Sch Informat Informat Forum Edinburgh EH8 9AB Midlothian Scotland Shanghai Jiao Tong Univ Dept Comp Sci & Engn 800 Dongchuan Rd Shanghai Peoples R China Shanghai Univ Finance & Econ ITCS 100 Wudong Rd Shanghai Peoples R China Shanghai Jiao Tong Univ John Hopcroft Ctr Comp Sci 800 Dongchuan Rd Shanghai Peoples R China

ISBN: (纸本)9781611975482

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second order recurrence modulo a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. this is in sharp contrast to the computational phase transition shown by 2-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting. We also use the "winding" technique to deduce the second result on cubic graphs.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

30th annual acm-siam symposium on discrete algorithms, SODA 2019

the proceedings contain 183 papers. the topics discussed include: fine-grained complexity meets IP = PSPACE;an equivalence class for orthogonal vectors;seth-based lower bounds for subset sum and bicriteria path;fast modular subset sum using linear sketching;a subquadratic approximation scheme for partition;metrical task systems on trees via mirror descent and unfair gluing;a nearly-linear bound for chasing nested convex bodies;dynamic double auctions: towards first best;and multi-unit supply-monotone auctions with Bayesian valuations.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Optimal Construction of Compressed Indexes for Highly Repetitive Texts 30

Optimal Construction of Compressed Indexes for Highly Repeti...

引用

30th annual acm-siam symposium on discrete algorithms (SODA)

作者： Kempa, Dominik Univ Helsinki Helsinki Inst Informat Technol HIIT Dept Comp Sci Helsinki Finland Univ Warwick Dept Comp Sci Coventry England Univ Warwick Ctr Discrete Math & its Applicat DIMAP Coventry England

ISBN: (纸本)9781611975482

We propose algorithms that, given the input string of length n over integer alphabet of size sigma, construct the Burrows{Wheeler transform (BWT), the permuted longest-common-prefix (PLCP) array, and the LZ77 parsing in O(n= log(sigma) n + r polylog n) time and working space, where r is the number of runs in the BWT of the input. these are the essential components of many compressed indexes such as compressed suffix tree, FM-index, and grammar and LZ77-based indexes, but also find numerous applications in sequence analysis and data compression. the value of r is a common measure of repetitiveness that is significantly smaller than n if the string is highly repetitive. Since just accessing every symbol of the string requires Omega(n/ log(sigma) n) time, the presented algorithms are time and space optimal for inputs satisfying the assumption n=r is an element of(polylog n) on the repetitiveness. For such inputs our result improves upon the currently fastest general algorithms of Belazzougui (STOC 2014) and Munro et al. (SODA 2017) which run in O(n) time and use O(n= log(sigma) n) working space. We also show how to use our techniques to obtain optimal solutions on highly repetitive data for other fundamental string processing problems such as: Lyndon factorization, construction of run-length compressed suffix arrays, and some classical \textbook" problems such as computing the longest substring occurring at least some fixed number of times.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Dimension-independent Sparse Fourier Transform 30

Dimension-independent Sparse Fourier Transform

引用

30th annual acm-siam symposium on discrete algorithms (SODA)

作者： Kapralov, Michael Velingker, Ameya Zandieh, Amir Ecole Polytech Fed Lausanne Sch Comp & Commun Sci Lausanne Switzerland Google Res Mountain View CA USA

ISBN: (纸本)9781611975482

the discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm. One remarkable feature of FFT is the fact that its runtime depends only on the size N of the input vector, but not on the dimensionality of the input domain: FFT runs in time O(N logN) irrespective of whether the DFT in question is on Z(N) or Z(d)(n) for some d > 1, where N = n(d). the state of the art for Sparse FFT, i.e. the problem of computing the DFT of a signal that has at most k nonzeros in Fourier domain, is very different: all current techniques for sublinear time computation of Sparse FFT incur an exponential dependence on the dimension d in the runtime. In this paper we give the first algorithm that computes the DFT of a k-sparse signal in time poly(k;logN) in any dimension d, avoiding the curse of dimensionality inherent in all previously known techniques. Our main tool is a new class of filters that we refer to as adaptive aliasing filters: these filters allow isolating frequencies of a k-Fourier sparse signal using O(k) samples in time domain and O(k logN) runtime per frequency, in any dimension d. We also investigate natural average case models of the input signal: worst case support in Fourier domain with randomized values and random locations in Fourier domain with worst case signal values. Our techniques lead to an (O) over tilde (k(2)) time algorithm for the former and an (O) over tilde (kappa) time algorithm for the latter.

关键词： discrete Fourier transforms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：