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

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

157 篇 会议
20 篇 期刊文献
1 册 图书

馆藏范围

178 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

112 篇 工学
- 107 篇 计算机科学与技术...
- 18 篇 软件工程
- 5 篇 信息与通信工程
- 3 篇 电气工程
- 2 篇 控制科学与工程
- 2 篇 化学工程与技术
- 1 篇 力学（可授工学、理...
- 1 篇 机械工程
- 1 篇 材料科学与工程（可...
- 1 篇 农业工程
- 1 篇 生物医学工程（可授...
- 1 篇 生物工程
103 篇 理学
- 101 篇 数学
- 9 篇 统计学（可授理学、...
- 2 篇 物理学
- 2 篇 化学
- 2 篇 系统科学
- 1 篇 生物学
6 篇 管理学
- 5 篇 管理科学与工程(可...
- 4 篇 工商管理
- 1 篇 图书情报与档案管...
3 篇 经济学
- 3 篇 应用经济学
1 篇 农学
- 1 篇 作物学

主题

14 篇 approximation al...
13 篇 algorithms
9 篇 polynomial appro...
4 篇 mobile agents
4 篇 discrete fourier...
3 篇 trees (mathemati...
3 篇 graphic methods
3 篇 logarithm (log)
3 篇 logs
3 篇 discrete mathema...
2 篇 computer science
2 篇 generating funct...
2 篇 fourier analysis
2 篇 byzantine agreem...
2 篇 problem solving
2 篇 average-case ana...
2 篇 planted clique
2 篇 probability dist...
2 篇 lower bound
2 篇 mixtures

机构

6 篇 univ alberta dep...
6 篇 rhein westfal th...
4 篇 univ new mexico ...
3 篇 university of wi...
3 篇 univ quebec outa...
3 篇 univ so calif de...
3 篇 univ bristol dep...
3 篇 univ bonn res in...
2 篇 university of ca...
2 篇 rhein westfal th...
2 篇 university of ed...
2 篇 department of ma...
2 篇 univ bonn hausdo...
2 篇 univ calif berke...
2 篇 rhein westfal th...
2 篇 department of co...
2 篇 bar ilan univ de...
2 篇 univ warwick dep...
2 篇 department of co...
2 篇 max planck inst ...

作者

9 篇 csaba d. tóth
7 篇 salavatipour moh...
5 篇 adrian dumitresc...
5 篇 svitkina zoya
5 篇 pelc andrzej
4 篇 friggstad zachar...
4 篇 sanwalani vishal
4 篇 king valerie
4 篇 saia jared
4 篇 andrzej pelc
3 篇 coja-oghlan amin
3 篇 kempe david
3 篇 diakonikolas ili...
3 篇 o'donnell ryan
3 篇 englert matthias
3 篇 servedio rocco a...
3 篇 clifford raphael
3 篇 tóth csaba d.
3 篇 grohe martin
2 篇 chan siu-on

语言

177 篇 英文
1 篇 其他

检索条件"任意字段=8th Annual ACM/SIAM Symposium on Discrete Algorithms"

共 178 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

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

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

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Deep Weisfeiler Leman 32

Deep Weisfeiler Leman

引用

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

作者： Grohe, Martin Schweitzer, Pascal Wiebking, Daniel Rhein Westfal TH Aachen Aachen Germany TU Kaiserslautern Kaiserslautern Germany

ISBN: (纸本)9781611976465

We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. We prove that, as an abstract computational model, polynomial-time DeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999). It is a well-known open question whether the existence of a polynomial-time graph isomorphism test implies the existence of a polynomial-time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomialtime DeepWL isomorphism test, then there is a polynomialtime canonisation algorithm for this class. this implies that there is also a logic capturing polynomial time on this class.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共18页 << < 1 2 3 4 5 6 7 8 9 10 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：