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

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Weisfeiler-Leman and Graph Spectra 34

Weisfeiler-Leman and Graph Spectra

引用

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

作者： Rattan, Gaurav Seppelt, Tim Rhein Westfal TH Aachen Aachen Germany

ISBN: (纸本)9781611977554

Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker than isomorphism. In this paper, we study cospectrality in relation to another well-studied relaxation of isomorphism, namely k-dimensional Weisfeiler-Leman ( k-WL) indistinguishability. Cospectrality with respect to standard graph matrices such as the adjacency or the Laplacian matrix yields a strictly finer equivalence relation than 2-WL indistinguishability. We show that individualising one vertex plus running 1-WL already subsumes cospectrality with respect to all such graph matrices. Building on this result, we resolve an open problem of Furer (2010) about spectral invariants and strengthen a result of Godsil (1981) about commute distances. Looking beyond 2-WL, we devise a hierarchy of graph matrices generalising the adjacency matrix such that k-WL indistinguishability after a fixed number of iterations can be captured as a spectral condition on these matrices. Precisely, we provide a spectral characterisation of k-WL indistinguishability after d iterations, for k;d is an element of N. Our results can be viewed as characterisations of homomorphism indistinguishability over certain graph classes in terms of matrix equations. the study of homomorphism indistinguishability is an emerging field, to which we contribute by extending the algebraic framework of Mancinska and Roberson (2020) and Grohe et al. (2022).

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Approximate Evaluation of First-Order Counting Queries 32

Approximate Evaluation of First-Order Counting Queries

引用

32nd annual acm-siam symposium on discrete algorithms (SODA)

作者： Dreier, Jan Rossmanith, Peter Rhein Westfal TH Aachen Aachen Germany

ISBN: (纸本)9781611976465

Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. they showed that there is an efficient model-checking algorithm on graphs with bounded degree, while Grohe and Schweikardt showed that probably no such algorithm exists for trees of bounded depth. We analyze the fragment FO({>0}) of this logic. While we remove for example subtraction and comparison between two nonatomic counting terms, this logic remains quite expressive: We allow nested counting and comparison between counting terms and arbitrarily large numbers. Our main result is an approximation scheme of the model-checking problem for FO({> 0}) that runs in linear fpt time on structures with bounded expansion. this scheme either gives the correct answer or says "I do not know." the latter answer may only be given if small perturbations in the number-symbols of the formula could make it both satisfied and unsatisfied. this is complemented by showing that exactly solving the model-checking problem for FO({> 0}) is already hard on trees of bounded depth and just slightly increasing the expressiveness of FO({> 0}) makes even approximation hard on trees.

关键词： Model checking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：