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

35th annual acm-siam symposium on discrete algorithms, SODA 2024

The proceedings contain 192 papers. The topics discussed include: prior-independent auctions for heterogeneous bidders;impossibilities for obviously strategy-proof mechanisms;revenue maximization for buyers with costly participation;breaking the 3/4 barrier for approximate maximin share;combinatorial contracts beyond gross substitutes;on supermodular contracts and dense subgraphs;sorting pattern-avoiding permutations via 0–1 matrices forbidding product patterns;vertical decomposition in 3D and 4D with applications to line nearest-neighbor searching in 3D;dynamic dictionary with subconstant wasted bits per key;dynamic time warping;and dynamically maintaining the persistent homology of time series.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Single-Source Unsplittable Flows in Planar Graphs 35

Single-Source Unsplittable Flows in Planar Graphs

引用

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

作者： Traub, Vera Koch, Laura Vargas Zenklusen, Rico Univ Bonn Res Inst Discrete Math Bonn Germany Univ Bonn Hausdorff Ctr Math Bonn Germany Swiss Fed Inst Technol Dept Math Zurich Switzerland

ISBN: (纸本)9781611977912

The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. This intriguing conjecture remains open. More so, there are arguably no non-trivial graph classes for which it is known to hold. We show that a slight weakening of it (with at most twice as large violations) holds for planar graphs. Our result is based on a connection to a highly structured discrepancy problem, whose repeated resolution allows us to successively reduce the number of paths used for each terminal, until we obtain an unsplittable flow. Moreover, our techniques also extend to simultaneous upper and lower bounds on the flow values. This also affirmatively answers a conjecture of Morell and Skutella for planar SSUF.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Kernelization for Graph Packing Problems via Rainbow Matching 34

Kernelization for Graph Packing Problems via Rainbow Matchin...

引用

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

作者： Bessy, Stephane Bougeret, Marin Thilikos, Dimitrios M. Wiederrecht, Sebastian Univ Montpellier CNRS LIRMM Montpellier France Inst for Basic Sci Korea Discrete Math Grp Daejeon South Korea

ISBN: (纸本)9781611977554

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the Induced 2-Path-Packing (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomasse, Zehavi. acm Trans. algorithms, 2019], where they gave a kernel of O(k(3/2)) vertices and O(k(5/3)) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of k(1+ O(1)/root log k) vertices and that I2PP admits a kernel of O(k) vertices.

关键词： Kernelization Parameterized algorithms Rainbow matching Packing problems

来源：评论

学校读者我要写书评

暂无评论

Packing cycles in planar and bounded-genus graphs 34

Packing cycles in planar and bounded-genus graphs

引用

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

作者： Schlomberg, Niklas Thiele, Hanjo Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany Univ Bonn Hausdorff Ctr Math Bonn Germany Greenplan GmbH Bonn Germany Swiss Fed Inst Technol FIM Zurich Switzerland

ISBN: (纸本)9781611977554

We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. The family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for an oracle access that finds a weight-minimal cycle in that family for given nonnegative edge weights or (in planar graphs) the union of all remaining cycles in that family after deleting a given subset of edges. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertex-disjoint paths. We also obtain approximate min-max theorems of the Erd}os{Posa type. For example, the minimum feedback vertex set in a planar digraph is at most 12 times the maximum number of vertex-disjoint cycles.

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

Fast and Accurate Approximations of the Optimal Transport in Semi-discrete and discrete Settings 35

Fast and Accurate Approximations of the Optimal Transport in...

引用

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

作者： Agarwal, Pankaj K. Raghvendra, Sharath Shirzadian, Pouyan Yao, Keegan Duke Univ Dept Comp Sci Durham NC 27706 USA North Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA Virginia Tech Dept Comp Sci Blacksburg VA USA

ISBN: (纸本)9781611977912

Given a d-dimensional continuous (resp. discrete) probability distribution mu and a discrete distribution nu, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from mu to nu;we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees. (i) Additive approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= cent(tau*) + epsilon in n(O(d)) log D/epsilon time;here, tau* is the optimal transport plan, D is the diameter of the supports of mu and nu, and we assume we have access to an oracle that outputs the mass of mu inside a constant-complexity region in O(1) time. Our algorithm works for several ground distances including the L-p-norm and the squared-Euclidean distance. (ii) Relative approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) in n log(n) . (epsilon(-1) log log n)(O(d)) expected time;here, tau* is the optimal transport plan, and we assume we have access to an oracle that outputs the mass of mu inside an orthogonal box in O(1) time, and the ground distance is any L-p norm. (iii) Relative approximation for discrete OT: For any parameter epsilon > 0, we present a Monte-Carlo algorithm that computes a transport plan (tau) over tilde with an expected cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) under any L-p norm in n log(n) . (epsilon(-1) log log n)(O(d)) time;here, tau* is an optimal transport plan and we assume that the spread of the supports of mu and nu is polynomially bounded.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Excluding Single-Crossing Matching Minors in Bipartite Graphs 34

Excluding Single-Crossing Matching Minors in Bipartite Graph...

引用

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

作者： Giannopoulou, Archontia C. Thilikos, Dimitrios M. Wiederrecht, Sebastian Natl & Kapodistrian Univ Athens Dept Informat & Telecommun Athens Greece Univ Montpellier CNRS LIRMM Montpellier France Inst for Basic Sci Korea Discrete Math Grp Daejeon South Korea

ISBN: (纸本)9781611977554

By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 P ' olya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K-3,K-3 as a matching minor. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K-3,K-3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0, 1)-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K-3,K-3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K5,5 as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes 2024

Near-Optimal Streaming Ellipsoidal Rounding for General Conv...

引用

56th annual acm symposium on Theory of Computing (STOC)

作者： Makarychev, Yury Manoj, Naren Sarayu Ovsiankin, Max Toyota Technol Inst Chicago IL 60637 USA

ISBN: (纸本)9798400703836

We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.

关键词： Ellipsoidal rounding John ellipsoid Convex polytopes Convex geometry discrete geometry Streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

34th annual acm-siam symposium on discrete algorithms, SODA 2023

34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ...

引用

34th annual acm-siam symposium on discrete algorithms, SODA 2023

ISBN: (纸本)9781611977554

The proceedings contain 189 papers. The topics discussed include: dynamic algorithms for packing-covering LPs via multiplicative weight updates;maintaining expander decompositions via sparse cuts;fully dynamic exact edge connectivity in sublinear time;faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths;dynamic matching with better-than-2 approximation in polylogarithmic update time;dynamic algorithms for maximum matching size;closing the gap between directed hopsets and shortcut sets;maximal k-edge-connected subgraphs in weighted graphs via local random contraction;faster and unified algorithms for diameter reducing shortcuts and minimum chain cover;near-linear time approximations for cut problems via fair cuts;fast discrepancy minimization with hereditary guarantees;a tight quasi-polynomial bound for global label min-cut;a tight quasi-polynomial bound for global label min-cut;a nearly-tight analysis of multipass pairing heaps;a tight analysis of slim heaps and smooth heaps;and short synchronizing words for random automata.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Rigorous Upper Bound for the discrete Bak-Sneppen Model

引用

JOURNAL OF STATISTICAL PHYSICS 2022年第1期186卷 1-10页

作者： Volkov, Stanislav Lund Univ Ctr Math Sci Box 118 S-22100 Lund Sweden

Fix some p is an element of[0, 1] and a positive integer n. The discrete Bak-Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a minimum element (typically, zero) is chosen with equal probability, and it is then replaced alongside both its neighbours by independent Bernoulli(p) random variables. Let nu((n))(p) be the probability that an element of this sequence equals one under the stationary distribution of this Markov chain. It was shown in Barbay and Kenyon (in proceedings of the Twelfth annual acm-siam symposium on discrete algorithms (Washington, DC, 2001), pp. 928-933, siam, Philadelphia, PA, 2001) that nu((n))(p) -> 1 as n -> infinity when p > 0.54...;the proof there is, alas, not rigorous. The complimentary fact that lim sup(n -> infinity)nu((n))(p) < 1 for p is an element of(0, p') for some p' > 0 is much harder;this was eventually shown in Meester and Znamenski (J Stat Phys 109:987-1004, 2002). The purpose of this note is to provide a rigorous proof of the result from Barbay and Kenyon (in proceedings of the Twelfth annual acm-siam symposium on discrete algorithms (Washington, DC, 2001), pp. 928-933, siam, Philadelphia, PA, 2001), as well as to improve it, by showing that nu((n))(p) -> 1 when p > 0.45. (Our method, in fact, shows that with some finer tuning the same is true for p > 0.419533.)

关键词： Bak-Sneppen model Self-organized criticality Renewal theory

来源：评论

学校读者我要写书评

暂无评论

IMPROVED CLASSICAL AND QUANTUM algorithms FOR THE SHORTEST VECTOR PROBLEM VIA BOUNDED DISTANCE DECODING

引用

siam JOURNAL ON COMPUTING 2025年第2期54卷 233-278页

作者： Aggarwal, Divesh Chen, Yanlin Kumar, Rajendra Shen, Yixin Ctr Quantum Technol Singapore 117543 Singapore Natl Univ Singapore Singapore 117543 Singapore QuSoft Amsterdam Netherlands CWI Amsterdam Netherlands Indian Inst Technol Delhi New Delhi 110016 India Univ Rennes Inria CNRS IRISA F-35040 Rennes France

The most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 \leq q \leq root n, our algorithm takes q13n+o(n) time and requires poly(n) \cdot q16n/q2 memory. This tradeoff, which ranges from enumeration (q = root n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in proceedings of the Forty-Seventh annual acm on symposium on Theory of Computing (STOC), 2015, pp. 733--742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285--306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRA

关键词： lattices shortest vector problem discrete Gaussian sampling time-space tradeoff quantum computation bounded distance decoding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：