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

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

the proceedings contain 146 papers. the topics discussed include: locality-sensitive hashing without false negatives;new directions in nearest neighbor searching with applications to lattice sieving;phase transitions in group testing;tight bounds for the distribution-free testing of monotone conjunctions;designing networks with good equilibria under uncertainty;characterization of strongly stable matchings;learning and efficiency in games with dynamic population;on dynamic approximate shortest paths for planar graphs with worst case costs;error amplification for pairwise spanner lower bounds;on notions of distortion and an almost minimum spanning tree with constant average distortion;approximately efficient double auctions with strong budget balance;and interpolating between truthful and non-truthful mechanisms for combinatorial auctions.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

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

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

关键词：

来源：评论

学校读者我要写书评

暂无评论

Blocking optimal κ-Arborescences 27

Blocking optimal κ-Arborescences

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

作者： Bernáth, Attila Király, Tamás MTA-ELTE Egervary Research Group Department of Operations Research Eotvos University Pazmany Peter Setany L/C BudapestH-1117 Hungary

ISBN: (纸本)9781510819672

Given a digraph D = (V,A) and a positive integer k, an arc set F ⊆ A is called a κ-arborescence if it is the disjoint union of k spanning arborescences. the problem of finding a minimum cost A'-arborescence is known to be polynomial-time solvable using matroid intersection. In this paper we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost fc-arborescence. For k = 1, the problem was solved in [A. Bernáth, G. Pap, Blocking optimal arborescences, IPCO 2013]. In this paper we give an algorithm for general k that has polynomial running time if k is fixed. © (2016) by siam: Society for Industrial and Applied Mathematics.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

New Approximation algorithms for the Unsplittable Capacitated Facility Location Problem

引用

ALGORIthMICA 2016年第1期75卷 53-83页

作者： Behsaz, Babak Salavatipour, Mohammad R. Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Google Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. this problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. this problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual acm-siam symposium on discrete algorithms, pp 805-814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria -approximations where the algorithm returns a solution whose cost is within factor of the optimum and violates the capacity constraints within factor . Shmoys et al. (Proceedings of the twenty-ninth annual acm symposium on theory of computing, pp 265-274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply (O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). these are the first algorithms with constant approximation in which the viol

关键词： Approximation algorithms Capacitated facility location Hard capacities

来源：评论

学校读者我要写书评

暂无评论

discrete Gaussian sampling reduces to CVP and SVP 27

Discrete Gaussian sampling reduces to CVP and SVP

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

作者： Stephens-Davidowitz, Noah New York University United States

ISBN: (纸本)9781510819672

the discrete Gaussian D⌊-t,s is the distribution that assigns to each vector x in a shifted lattice ⌊ - t probability proportional to e-π||x||2/s2 It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters s have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggar-wal, Dadush, Regev, and Stephens-Davidowitz showed 2n+o(n)-time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. there is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when t = 0) to SVP. In the other direction, there is a simple reduction from 7-approximate SVP for any γ = ω(√n/logn), and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. © (2016) by siam: Society for Industrial and Applied Mathematics.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform 27

Nearly optimal deterministic algorithm for sparse Walsh-Hada...

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

作者： Cheraghchi, Mahdi Indyk, Piotr Department of Computing Imperial College London United Kingdom MIT Computer Science and Artificial Intelligence Laboratory CambridgeMA02139 United States

ISBN: (纸本)9781510819672

For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., discrete Fourier Transform over the Boolean cube) of an iV-dimensional vector x ∈ N in time k1+α(log N)°(1) Specifically, the algorithm is given query access to x and computes a k-sparse x ∈ .N satisfying ||x-◯||1 ≤ c||◯ - Hk(◯)\\1, for an absolute constant c > 0, where x is the transform of x and Hk(x) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, Jacm 2009). Moreover, we design a deterministic and non-adaptive l1/l1 compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k1+α(logN)O(1) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion;therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k(log N)(1) reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter α). By allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to Ō(k log3 N).

关键词： discrete Fourier transforms

来源：评论

学校读者我要写书评

暂无评论

Directed multicut is W-hard, even for four terminal pairs 16

Directed multicut is W-hard, even for four terminal pairs

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Marcin Pilipczuk Magnus Wahlstrom University of Warsaw Royal Holloway University of London

ISBN: (纸本)9781510819672

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. this negative result almost completely resolves one of the central open problems in the area of parameterized complexity of graph separation problems, posted originally by Marx and Razgon [siam J. Comput. 43(2):355-388 (2014)], leaving only the case of three terminal pairs open. the case of two terminal pairs was shown to be FPT by Chitnis et al. [siam J. Comput. 42(4):1674-1696 (2013)]. Our gadget methodology also allows us to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [siam J. discrete Math. 27(3):1503-1513 (2013)].

关键词： multicut less-favoured region directed graphs parameterization iodine Device Terminal discrete mathematics

来源：评论

学校读者我要写书评

暂无评论

discrete Gaussian Sampling Reduces to CVP and SVP 16

Discrete Gaussian Sampling Reduces to CVP and SVP

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Noah Stephens-Davidowitz New York University

ISBN: (纸本)9781510819672

the discrete Gaussian D_(L-t,s) is the distribution that assigns to each vector x in a shifted lattice L - t probability proportional to e~(-π‖x‖~2/s~2). It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomialtime algorithms for DGS with very high parameters s have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed 2~(n+o(n))-time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. there is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when t = 0) to SVP. In the other direction, there is a simple reduction from g-approximate SVP for any γ = Ω({the square root of}(n/log n)), and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor.

关键词： DiGeorge Syndrome COP protocol 2 SVP computer science

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the 25th annual acm-siam symposium on discrete algorithms, SODA 2014

Proceedings of the 25th Annual ACM-SIAM Symposium on Discret...

引用

25th annual acm-siam symposium on discrete algorithms, SODA 2014

ISBN: (纸本)9781611973389

the proceedings contain 136 papers. the topics discussed include: a constant factor approximation algorithm for fault-tolerant k-median;improved approximation algorithm for two-dimensional bin packing;a mazing 2+eps approximation for unsplittable flow on a path;better approximation bounds for the joint replenishment problem;better algorithms and hardness for broadcast scheduling via a discrepancy approach;an excluded grid theorem for digraphs with forbidden minors;finding small patterns in permutations in linear time;minimum common string partition parameterized by partition size is fixed-parameter tractable;interval deletion is fixed-parameter tractable;efficient computation of representative sets with applications in parameterized and exact algorithms;and on the computational complexity of betti numbers: reductions from matrix rank.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform 16

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hada...

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Mahdi Cheraghchi Piotr Indyk Department of Computing Imperial College London MIT Computer Science and Artificial Intelligence Laboratory

ISBN: (纸本)9781510819672

For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x ∈ R~N in time k~(1+α)(logN)~(O(1)). Specifically, the algorithm is given query access to x and computes a k-sparse ～x ∈ R~N satisfying ‖x - x‖1 ≤ ‖x - H_k(x)‖1, for an absolute constant c > 0, where x is the transform of x and H_k(x) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, Jacm 2009). Moreover, we design a deterministic and non-adaptive l_1/l_1 compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k~(1+α)(logN)~(O(1)) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k(logN)~(O(1)) reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter α). By allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to ～O(k log~3 N).

关键词： Condensers mechanical heart valve algorithms Hadamard transform Lossless Transform deterministic algorithms discrete Fourier transform deterministic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：