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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

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

引用

30th annual acm-siam symposium on discrete algorithms, SODA 2019

the proceedings contain 183 papers. the topics discussed include: fine-grained complexity meets IP = PSPACE;an equivalence class for orthogonal vectors;seth-based lower bounds for subset sum and bicriteria path;fast modular subset sum using linear sketching;a subquadratic approximation scheme for partition;metrical task systems on trees via mirror descent and unfair gluing;a nearly-linear bound for chasing nested convex bodies;dynamic double auctions: towards first best;and multi-unit supply-monotone auctions with Bayesian valuations.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Directed Tangle Tree-Decompositions and Applications 33

Directed Tangle Tree-Decompositions and Applications

引用

annual acm-siam symposium on discrete algorithms (SODA)

作者： Giannopoulou, Archontia C. Kawarabayashi, Ken-ichi Kreutzer, Stephan Kwon, O-joung Natl & Kapodistrian Univ Athens Dept Informat & Telecommun Athens Greece Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Tech Univ Berlin Sekr 7-3Ernst Reuter Pl 7 D-10587 Berlin Germany Incheon Natl Univ Dept Math Incheon South Korea Inst Basic Sci IBS Discrete Math Grp Daejeon South Korea

ISBN: (纸本)9781611977073

the tangle tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs G that distinguishes all maximal directed tangles in G. Furthermore, for any integer k, we construct a directed tree-decomposition that distinguishes all directed tangles of order k. By relaxing the bound slightly, we can make the previous result algorithmic: for fixed k, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order 6k - 1 separated by some separation of order less than k. As a direct application of the tangle tree-decomposition theorem, we prove that for every fixed k there is a polynomial-time algorithm which, on input G, and source and sink vertices (s(1), t(1)), ..., (s(k), t(k)), either finds a family of paths P-1,..., P-k such that each P-i links s(i) to t(i) and every vertex of G is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting s(i) to t(i). this result improves previous results (with "two" replaced by "three"), and given known hardness results, our result cannot be extended to fixed parameter tractability nor fully vertex-disjoint directed paths.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

SIMPLE, DETERMINISTIC, CONSTANT-ROUND COLORING IN CONGESTED CLIQUE AND MPC

引用

siam JOURNAL ON COMPUTING 2021年第5期50卷 1603-1626页

作者： Czumaj, Artur Davies, Peter Parter, Merav Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat Coventry CV4 7AL W Midlands England IST Austria A-3400 Klosterneuburg Austria Weizmann Inst Sci IL-7610001 Rehovot Israel

We settle the complexity of the ( increment +1)-coloring and ( increment +1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. this matches the complexity of the recent breakthrough randomized constant-round ( increment + 1)-list coloring algorithm due to Chang et al. [Proceedings of the 38th acm symposium on Principles of Distributed Computing, 2019] and significantly improves upon the state-of-the-art O (log increment )-round deterministic ( increment + 1)-coloring bound of Parter [Proceedings of the 45th annual International Colloquium on Automata, Languages and Programming]. A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, and Pettie [Proceedings of the 50th annual acm SIGACT symposium on theory of Computing, 2018], our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O (1) recursion steps, the remaining uncolored subgraph within each bin has linear size and thus can be solved locally by collecting it to a single node. this algorithm can also be implemented in the massively parallel computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime, in which machines have sublinear space: we present the first deterministic ( increment + 1)-list coloring algorithm designed for sublinear-space MPC, which runs in O (log increment + log log n) rounds.

关键词： congested clique massively parallel computation coloring derandomization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：