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

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

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Fac Elect Engn Karlovo Namesti 13 Prague 12135 Czech Republic

ISBN: (纸本)9781611974782

We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is as hard as solving the general LP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation of each of these problems. this result poses a fundamental limitation for designing efficient algorithms to solve the LP relaxations, because finding such an algorithm might improve the complexity of best known algorithms for the general LP. Besides linear-time reductions, we show that the LP relaxations of the considered problems are P-complete under log-space reduction, therefore also hard to parallelize.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

Metric embeddings with outliers 28

Metric embeddings with outliers

引用

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

作者： Sidiropoulos, Anastasios Wang, Dingkang Wang, Yusu Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Ohio State Univ Dept Math 231 W 18th Ave Columbus OH 43210 USA

ISBN: (纸本)9781611974782

We initiate the study of metric embeddings with outliers. Given some finite metric space we wish to remove a small set of points and to find either an isometric or a low-distortion embedding of the remaining points into some host metric space. this is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. We present polynomial-time approximation algorithms for computing outlier embeddings into Euclidean space, trees, and ultrametrics. In the case of isometric embeddings the objective is to minimize the number of outliers, while in the case of non-isometrics we have a bi-criteria optimization problem where the goal is to minimize both the number of outliers and the distortion. We complement our approximation algorithms with NP-hardness results for these problems. We conclude with a brief experimental evaluation of our non-isometric outlier embedding on synthetic and real-world data sets.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism 28

Linear Diophantine Equations, Group CSPs, and Graph Isomorph...

引用

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

作者： Berkholz, Christoph Grohe, Martin Humboldt Univ Berlin Germany Rhein Westfal TH Aachen Aachen Germany

ISBN: (纸本)9781611974782

In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Grobner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of non-isomorphic CFI-graphs (introduced by Cai, Furer, and Immerman in 1992 as hard examples for the combinatorial Weisfeiler-Leman algorithm) cannot be distinguished by these mathematical algorithms. A notable exception were the algebraic algorithms over the field F-2 for which no lower bound was known. Another, in some way even stronger, approach to graph isomorphism testing is based on solving systems of linear Diophantine equations (that is, linear equations over the integers), which is known to be possible in polynomial time. So far, no lower bounds for this approach were known. Lower bounds for the algebraic algorithms can best be proved in the framework of proof complexity, where they can be phrased as lower bounds for algebraic proof systems such as Nullstellensatz or the (more powerful) polynomial calculus. We give new hard examples for these systems: families of pairs of non-isomorphic graphs that are hard to distinguish by polynomial calculus proofs simultaneously over all prime fields, including F2, as well as examples that are hard to distinguish by the systems-of-linear-Diophantine-equations approach. In a previous paper, we observed that the CFI-graphs are closely related to what we call "group CSPs": constraint satisfaction problems where the constraints are membership tests in some coset of a subgroup of a cartesian power of a base group (Z(2) in the case of the classical CFI-graphs). Our new examples are also based on group CSPs (for Abelian groups), but here we extend the CSPs by a few non-group constraints to obtain even harder instances for graph isomorphism.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Reordering Buffers with Logarithmic Diameter Dependency for Trees 28

Reordering Buffers with Logarithmic Diameter Dependency for ...

引用

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

作者： Englert, Matthias Racke, Harald Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry W Midlands England Tech Univ Munich Dept Informat Munich Germany

ISBN: (纸本)9781611974782

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. the goal is to process all items while minimizing the total distance the server moves. Englert, Racke, Westermann (STOC'07) gave a deterministic O(D . log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(log D+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h . (log D+log h)/k)competitive. For h = (1 + epsilon) . k, with constant epsilon > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n . log(2) k) result for n-point metric spaces from STOC'07 to O(log n . log k).

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

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

引用

28th annual acm-siam symposium on discrete algorithms, SODA 2017

ISBN: (纸本)9781611974782

the proceedings contain 181 papers. the topics discussed include: a framework for similarity search with space-time tradeoffs using locality-sensitive filtering;LSH forest: practical algorithms made theoretical;faster approximation schemes for the two-dimensional knapsack problem;split packing: an algorithm for packing circles with optimal worst-case density;local search for max-sum diversification;maximum scatter tsp in doubling metrics;exploring an infinite space with finite memory scouts;parameter-free locality sensitive hashing for spherical range reporting;distance sensitive bloom filters without false negatives;optimal approximate polytope membership;and massively-parallel similarity join, edge-isoperimetry, and distance correlations on the hypercube.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Scaling exponential backoff: Constant throughput, polylogarithmic channel-access attempts, and robustness

Scaling exponential backoff: Constant throughput, polylogari...

引用

作者： Bender, Michael A. Fineman, Jeremy T. Gilbert, Seth Young, Maxwell Department of Computer Science Office 245 Stony Brook University Stony BrookNY11794-2424 United States Department of Computer Science St. Mary's Hall Georgetown University 3700 O St. NW Office 346 WashingtonDC20057-1232 United States Department of Computer Science COM2-3-23 National University of Singapore 1 13 Computing Drive Office Singapore Department of Computer Science and Engineering Butler Hall Office 312 Mississippi State University 4665 George Perry Street MS39762 United States

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (1) it should provide constant throughput, wasting as little time as possible;(2) it should require few failed access attempts, minimizing the amount of wasted effort;and (3) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it can suffer subconstant throughput under bursty traffic, and it is not robust to adversarial disruption. the goal of this article is to "fix" exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an online, worst-case fashion. We present a relatively simple backoff protocol, Re-Backoff, that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. Re-Backoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, Re-Backoff provides the following guarantees. For n packets, the expected number of access attempts for successfully sending a packet is O(log2(n + D)). For the case of an infinite number of packets, we provide a similar result in terms of the maximum number of processes that are ever in the system concurrently. © 2018 Association for Computing Machinery.

关键词： Wireless networks

来源：评论

学校读者我要写书评

暂无评论

Better upper bounds on the Furedi{Hajnal limits of permutations 28

Better upper bounds on the Furedi{Hajnal limits of permutati...

引用

28th annual acm-siam symposium on discrete algorithms, SODA 2017

作者： Cibulka, Josef Kynč, Jan Department of Applied Mathematics and Institute for Theo- Retical Computer Science Faculty of Mathe- Matics and Physics Charles University Malostranské nám. 25 Praha 111800 Czech Republic Alfréd Rényi Institute of Mathematics Reáltanoda u. 13-15 Budapest1053 Hungary

ISBN: (纸本)9781611974782

A binary matrix is a matrix with entries from the set f0;1g. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries. If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k × k matrix with exactly one 1-entry in every row and one 1-entry in every column. the Furedi{Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant cP such that for every n 2 N, every n × n binary matrix A with at least cP n 1-entries contains P. We show that cP ≤ 2O(k2=3log7=3k=(loglogk)1=3) asymptotically almost surely for a random k-permutation matrix P. We also show that cP ≤ 2(4+o(1))k for every k- permutation matrix P, improving the constant in the exponent of a recent upper bound on cP by Fox. We also consider a higher-dimensional generalization of the Stanley{Wilf conjecture about the number of d- dimensional n-permutation matrices avoiding a fin-O(k)xed d- dimensional k-permutation matrix, and prove almost matching upper and lower bounds of the form (2-k)o(n)(n!)d-1-1=(d-1) and n-O(k)k(n). (n!)d-1-1=(d-1), respectively. Copyright © by siam.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

引用

acm TRANSACTIONS ON algorithms 2018年第3期14卷 28-28页

作者： Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Henry Raghavendra, Prasad Schramm, Tselil Cornell Univ 107 Hoy Rd Ithaca NY 14853 USA UT Austin Austin TX USA Univ Calif Berkeley 253 Cory Hall Berkeley CA 94720 USA Princeton Univ 35 Olden St Princeton NJ 08540 USA Univ Chicago 1100 East 58th St Chicago IL 60637 USA Harvard John A Paulson Sch Engn & Appl Sci Pierce Hall29 Oxford St Cambridge MA 02138 USA

the problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size omega >> log (n) added to an Erdos-Renyi graph G similar to G(n, 1/2), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size omega = Omega(root n). By contrast, information theoretically, one can recover planted cliques so long as omega >> log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless omega >> root n/polylog n, improving on the bound omega >> n(1/3) due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of References [2, 25, 27].

关键词： Sum of Squares method planted clique random matrices

来源：评论

学校读者我要写书评

暂无评论

Recognizing weak embeddings of graphs 18

Recognizing weak embeddings of graphs

引用

Proceedings of the Twenty-Ninth annual acm-siam symposium on discrete algorithms

作者： Hugo A. Akitaya Radoslav Fulek Csaba D. Tóth Tufts University Institute of Science and Technology Klosterneuburg Austria California State University Northridge and Tufts University

ISBN: (纸本)9781611975031

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. this raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding φε : G → M with [Equation] for every ε > 0.A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2ω) ≤ O(n4.75) time, where ω ≈ 2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually "untangles" the image ψ(G) into an embedding φ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Reordering Buffers with Logarithmic Diameter Dependency for Trees 17

Reordering Buffers with Logarithmic Diameter Dependency for ...

引用

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

作者： Matthias Englert Harald Racke Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick Department of Informatics Technical University Munich

ISBN: (纸本)9781510836358

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. the goal is to process all items while minimizing the total distance the server moves. Englert, Racke, Westermann (STOC'07) gave a deterministic O(D·log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(log D+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h·(log D+log h)/k)-competitive. For h = (1 + ε)·k, with constant ε > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n · log~2 k) result for n-point metric spaces from STOC'07 to O(log n·log k).

关键词： metric space Servers algorithms Optimization algorithms DEPENDENCE analysis of algorithm Logarithmic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：