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

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

作者： Sering, Leon Koch, Laura Vargas Tech Univ Berlin Inst Math Berlin Germany Rhein Westfal TH Aachen Sch Business & Econ Aachen Germany

ISBN: (纸本)9781611975482

Modeling traffic in road networks is a widely studied but challenging problem, especially under the assumption that drivers act selfishly. A common approach used in simulation software is the deterministic queuing model, for which the structure of dynamic equilibria has been studied extensively in the last couple of years. the basic idea is to model traffic by a continuous flow that travels over time from a source to a sink through a network, in which the arcs are endowed with transit times and capacities. Whenever the flow rate exceeds the capacity a queue builds up and the infinitesimally small flow particles wait in line in front of the bottleneck. Since the queues have no physical dimension, it was not possible, until now, to represent spillback in this model. this was a big drawback, since spillback can be regularly observed in real traffic situations and has a huge impact on travel times in highly congested regions. We extend the deterministic queuing model by introducing a storage capacity that bounds the total amount of flow on each arc. If an arc gets full, the inflow capacity is reduced to the current outflow rate, which can cause queues on previous arcs and blockages of intersections, i.e., spillback. We carry over the main results of the original model to our generalization and characterize dynamic equilibria, called Nash flows over time, by sequences of particular static flows, we call spillback thin flows. Furthermore, we give a constructive proof for the existence of dynamic equilibria, which suggests an algorithm for their computation. this solves an open problem stated by Koch and Skutella in 2010 [13].

关键词： Travel time

来源：评论

学校读者我要写书评

暂无评论

Approximating Spanners and Directed Steiner Forest

Approximating Spanners and Directed Steiner Forest

引用

作者： Chlamtáč, Eden Dinitz, Michael Kortsarz, Guy Laekhanukit, Bundit Ben Gurion University Be'er-Sheva Israel Johns Hopkins University United States Rutgers University-Camden United States Shanghai University of Finance 8 Economics China

It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA'16 8 ***'17, Bodwin-Williams SODA'16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances, we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O(n3/5 + ϵ)-approximation for distance preservers and pairwise spanners (for arbitrary constant ϵ > 0). this is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O(log n)-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O(1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O(n3/5 + ϵ)-approximation for the Directed Steiner Forest problem (for arbitrary constant ϵ > 0) when all edges have uniform costs, improving the previous best O(n2/3 + ϵ)-approximation due to Berman et al. [ICALP'11] (which holds for general edge costs). © 2020 acm.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On the cover of the rolling stone 20

On the cover of the rolling stone

引用

Proceedings of the thirty-First annual acm-siam symposium on discrete algorithms

作者： Adrian Dumitrescu Csaba D. Tóth University of Wisconsin-Milwaukee California State University Northridge

We construct a convex polytope of unit diameter that when placed on a horizontal surface on one of its faces, it repeatedly rolls over from one face to another until it comes to rest on some face, far away from its start position: that is, the horizontal distance between the footprints of the start and final faces can be larger than any given threshold. According to the laws of physics, the vertical distance between the center of mass of the polytope and the horizontal surface continuously decreases throughout the entire motion. the speed of the motion is irrelevant. Specifically, if the polytope is manually stopped after each tumble, the motion resumes when released (unless it stands on the final stable face).Moreover, such a polytope can be realized so that (i) it has a unique stable face, and (ii) it is an arbitrary close approximation of a unit ball. As such, this construction gives a positive answer to a question raised by Conway (1969).the arbitrarily large rolling distance property investigated here for the first time raises intriguing questions and opens new avenues for future research.

关键词： center of mass

来源：评论

学校读者我要写书评

暂无评论

Atomic embeddability, clustered planarity, and thickenability 20

Atomic embeddability, clustered planarity, and thickenabilit...

引用

Proceedings of the thirty-First annual acm-siam symposium on discrete algorithms

作者： Radoslav Fulek Csaba D. Tóth University of Arizona California State University

We study the atomic embeddability testing problem, which is a common generalization of clustered planarity (c-planarity, for short) and thickenability testing, and present a polynomial time algorithm for this problem, thereby giving the first polynomial time algorithm for c-planarity.C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently, despite relentless efforts. the thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial *** algorithm for atomic embeddability combines ideas from Carmesin's work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph *** we give a polynomial-time reduction from c-planarity to thickenability and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Cake cutting on graphs: a discrete and bounded proportional protocol 20

Cake cutting on graphs: a discrete and bounded proportional ...

引用

Proceedings of the thirty-First annual acm-siam symposium on discrete algorithms

作者： Xiaohui Bei Xiaoming Sun Hao Wu Jialin Zhang Zhijie Zhang Wei Zi Nanyang Technological University University of Chinese Academy of Sciences

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].

关键词：

来源：评论

学校读者我要写书评

暂无评论

Polycubes with Small Perimeter Defect 29

Polycubes with Small Perimeter Defect

引用

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

作者： Asinowski, Andrei Barequet, Gill Zheng, Yufei Vienna Univ Technol Inst Discrete Math & Geometry A-1040 Vienna Austria Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

A polycube is a face-connected set of cubical cells on Z(3). To-date, no formulae enumerating polycubes by volume (number of cubes) or perimeter (number of empty cubes neighboring the polycube) are known. We present a... 详细信息

ISBN: (纸本)9781611975031

关键词： Polycubes linear recurrence generating functions

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

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

引用

29th annual acm-siam symposium on discrete algorithms, SODA 2018

ISBN: (纸本)9781611975031

the proceedings contain 180 papers. the topics discussed include: dynamic algorithms for graph coloring;incremental DFS algorithms: a theoretical and experimental study;decremental transitive closure and shortest paths for planar digraphs and beyond;polycubes with small perimeter defect;the classical complexity of boson sampling;race detection and reachability in nearly series-parallel DAGs;the complexity of independent set reconfiguration on bipartite graphs;metric violation distance: hardness and approximation;a submodular measure and approximate Gomory-Hu theorem for packing odd trails;and minor-matching hypertree width.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Approaching 3/2 for the s-t-path TSP 29

Approaching 3/2 for the <i>s</i>-<i>t</i>-path TSP

引用

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

作者： Traub, Vera Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany

ISBN: (纸本)9781611975031

We show that there is a polynomial-time algorithm with approximation guarantee 3/2 + epsilon for the s-t-path TSP, for any fixed epsilon > 0. It is well known that Wolsey's analysis of Christofides' algorithm also works for the s-t-path TSP with its natural LP relaxation except for the narrow cuts ( in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut ( then call the edge and the cut lonely) or at least three ( then call the cut busy). Our algorithm "guesses" ( by dynamic programming) lonely cuts and edges. then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a k-stage recursive dynamic program, we can compute a spanning tree (V, S) and an LP solution y such that (1/2 + O(2(-k)))y is in the T-join polyhedron, where T is the set of vertices whose degree in S has the wrong parity.

关键词： Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL MEAN-BASED algorithms FOR TRACE RECONSTRUCTION

引用

ANNALS OF APPLIED PROBABILITY 2019年第2期29卷 851-874页

作者： De, Anindya O'Donnell, Ryan Servedio, Rocco A. Northwestern Univ Elect Engn & Comp Sci 2133 Sheridan Rd Evanston IL 60201 USA Carnegie Mellon Univ Sch Comp Sci 7213 Gates Ctr Pittsburgh PA 15213 USA Columbia Univ Comp Sci Dept 500 W 120th St New York NY 10027 USA

In the (deletion-channel) trace reconstruction problem, there is an unknown n-bit source string x. An algorithm is given access to independent traces of x, where a trace is formed by deleting each bit of x independently with probability delta. the goal of the algorithm is to recover x exactly (with high probability), while minimizing samples (number of traces) and running time. Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein et al. [in Proceedings of the Nineteenth annual acm-siam symposium on discrete algorithms 389-398 (2008) acm];it uses exp((O)over tild(n(1/2) )) samples and running time for any fixed 0 < delta < 1. It is also what we call a "mean-based algorithm," meaning that it only uses the empirical means of the individual bits of the traces. Holenstein et al. also gave a lower bound, showing that any mean-based algorithm must use at least n((Omega)over tild)(log n) samples. In this paper, we improve both of these results, obtaining matching upper and lower bounds for mean-based trace reconstruction. For any constant deletion rate 0 < delta < 1, we give a mean-based algorithm that uses exp(O(n(1/3))) time and traces;we also prove that any mean-based algorithm must use at least exp(Omega(n(1/3))) traces. In fact, we obtain matching upper and lower bounds even for delta subconstant and rho = 1 - delta subconstant: when (log(3)n)/n << delta <= 1/2 the bound is exp(-theta(delta n)(1/3)), and when 1/root n <the bound is exp(-theta(n/rho)(1/3)). Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks. We show that these techniques can also be used to perform trace reconstruction with random insertions and bit-flips in addition to deletions. We also find a surprising result: for deletion probabilities delta > 1/2, the presence of insertions can actually help with trace reconstruction.

关键词： Trace reconstruction deletion channel Littlewood polynomials

来源：评论

学校读者我要写书评

暂无评论

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

On the Integrality Gap of Degree-4 Sum of Squares for Plante...

引用

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

作者： 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

ISBN: (纸本)9781510819672

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：