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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

10 篇 会议

馆藏范围

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

日期分布

学科分类号

6 篇 理学
- 5 篇 数学
- 2 篇 系统科学
- 1 篇 统计学（可授理学、...
3 篇 工学
- 1 篇 机械工程
- 1 篇 仪器科学与技术
- 1 篇 控制科学与工程
- 1 篇 计算机科学与技术...
2 篇 管理学
- 1 篇 管理科学与工程(可...
- 1 篇 图书情报与档案管...

主题

1 篇 traveling salesm...
1 篇 runtime
1 篇 euclidean distan...
1 篇 access control
1 篇 approximation al...
1 篇 ant colony optim...
1 篇 electronic mail
1 篇 ganglia
1 篇 set theory
1 篇 information mana...
1 篇 connected compon...
1 篇 social network s...
1 篇 syntactics
1 篇 algorithm design...
1 篇 square root
1 篇 clocks
1 篇 shortest path
1 篇 optimization met...
1 篇 kernel
1 篇 time measurement

机构

1 篇 school of comput...
1 篇 department of co...
1 篇 computer science...
1 篇 department 1: al...
1 篇 department of co...
1 篇 school of operat...
1 篇 school of comput...
1 篇 max-planck-insti...
1 篇 department of al...
1 篇 theoretical divi...
1 篇 iinstitute of di...
1 篇 max-planck-insti...
1 篇 school of mathem...
1 篇 department 1: al...
1 篇 department 1: al...
1 篇 department 1 : a...
1 篇 department of co...
1 篇 am campus 1 klos...
1 篇 department of co...
1 篇 hamburg universi...

作者

2 篇 kötzing timo
2 篇 tobias friedrich
1 篇 mnich matthias
1 篇 neumann frank
1 篇 frank neumann
1 篇 rybicki joel
1 篇 goke alexander
1 篇 williamson david...
1 篇 koenemann jochen
1 篇 lenzen christoph
1 篇 thomas sauerwald
1 篇 ezra esther
1 篇 case john
1 篇 milan bradonjic
1 篇 sun hao
1 篇 khaled elbassion...
1 篇 drmota michael
1 篇 alexandre stauff...
1 篇 robert elsaesser
1 篇 elisa bertino

语言

10 篇 英文

检索条件"机构=Department 1: Algorithms and Complexity"

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

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

详细简洁

排序：

HITTING WEIGHTED EVEN CYCLES IN PLANAR GRAPHS

HITTING WEIGHTED EVEN CYCLES IN PLANAR GRAPHS

引用

作者： Goke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Combinatorics & Optimization University of Waterloo WaterlooONN2L 3G1 Canada

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family Ƒ. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153-180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748-759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584-597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191-204] showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. © 2022 Alexander Göke, Jochen Koenemann, Matthias Mnich, Hao Sun.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Self-stabilising Byzantine clock synchronisation is almost as easy as consensus

Self-stabilising Byzantine clock synchronisation is almost a...

引用

作者： Lenzen, Christoph Rybicki, Joel Department of Algorithms and Complexity Max Planck Institute for Informatics Saarland Informatics Campus Campus E1 4 Saarbrücken66123 Germany Am Campus 1 Klosterneuburg3400 Austria

We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f © 2019 Copyright held by the owner/author(s).

关键词： Clocks

来源：评论

学校读者我要写书评

暂无评论

Memory-limited non-U-shaped learning with solved open problems

Memory-limited non-U-shaped learning with solved open proble...

引用

作者： Case, John Kötzing, Timo Department of Computer and Information Science University of Delaware Newark DE 19716 United States Department 1: Algorithms and Complexity Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

In empirical cognitive science, for human learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, previous results have shown, for example, that such U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we also distinguish between semantic and syntactic U-shapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic U-shapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power. We analyze the necessity of U-shapes in two memory-limited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitly-bounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, U-shapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show that there is a class learnable memorylessly with a single feedback query such that this class is not learnable non-U-shapedly memorylessly with any finite number of feedback queries. We employ self-learning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion

关键词： Syntactics

来源：评论

学校读者我要写书评

暂无评论

Plateaus can be harder in multi-objective optimization

Plateaus can be harder in multi-objective optimization

引用

Congress on Evolutionary Computation

作者： Tobias Friedrich Nils Hebbinghaus Frank Neumann Department 1: Algorithms and Complexity Max Planck Institut für Informatik Saarbruecken Germany

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SETCOVER problem.

关键词： Evolutionary computation Polynomials Optimization methods Algorithm design and analysis Runtime Pareto optimization Time measurement

来源：评论

学校读者我要写书评

暂无评论

Ant colony optimization and the minimum cut problem 10

Ant colony optimization and the minimum cut problem

引用

12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010

作者： Kötzing, Timo Lehre, Per Kristian Neumann, Frank Oliveto, Pietro S. Department 1 : Algorithms and Complexity Max-Planck-Institut für Informatik 66123 Saarbrücken Germany School of Computer Science University of Birmingham B15 2TT Birmingham United Kingdom

ISBN: (纸本)9781450300728

Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts. Copyright 2010 ACM.

关键词： Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

A proof of the Boyd-Carr conjecture

A proof of the Boyd-Carr conjecture

引用

23rd Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2012

作者： Schalekamp, Frans Williamson, David P. Van Zuylen, Anke School of Operations Research and Information Engineering Cornell University Ithaca NY 14853 United States Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus El 4 66123 Saarbrücken Germany

ISBN: (纸本)9781611972108

Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP;they conjecture the ratio is at most 10/9. In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching. Copyright © SIAM.

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

A central limit theorem for the number of degree-k vertices in random maps 9

A central limit theorem for the number of degree-k vertices ...

引用

9th Meeting on Analytic Algorithmics and Combinatorics, ANALCO 2012

作者： Drmota, Michael Panagiotou, Konstantinos Iinstitute of Discrete Mathematics and Geometry TU Wien Wiedner Hauptstr. 8-10 WienA-1040 Austria Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus E1.4 Saarbrücken66123 Germany

ISBN: (纸本)9781618396235

We prove that the number of vertices of given degree in random planar maps satisfies a central limit theorem with mean and variance that are asymptotically linear in the number of edges. The proof relies on an analytic version of the quadratic method and singularity analysis of multivariate generating functions. © Copyright (2012) by SIAM: Society for Industrial and Applied Mathematics. All rights reserved.

关键词： Multivariant analysis

来源：评论

学校读者我要写书评

暂无评论

Modeling the Risk & Utility of Information Sharing in Social Networks

Modeling the Risk & Utility of Information Sharing in Social...

引用

IEEE International Conference on and IEEE International Confernece on Social Computing (SocialCom) Privacy, Security, Risk and Trust (PASSAT)

作者： Mohamed R. Fouad Khaled Elbassioni Elisa Bertino Department of Computer Science Purdue University West Lafayette IN USA Department 1: Algorithms and Complexity Max-Planck-Institute for Informatics Saarbrcken Germany

With the widespread of social networks, the risk of information sharing has become inevitable. Sharing a user's particular information in social networks is an all-or-none decision. Users receiving friendship invitations from others may decide to accept this request and share their information or reject it in which case none of their information will be shared. Access control in social networks is a challenging topic. Social network users would want to determine the optimum level of details at which they share their personal information with other users based on the risk associated with the process. In this paper, we formulate the problem of data sharing in social networks using two different models: (i) a model based on \emph{diffusion kernels}, and (ii) a model based on access control. We show that it is hard to apply the former in practice and explore the latter. We prove that determining the optimal levels of information sharing is an NP-hard problem and propose an approximation algorithm that determines to what extent social network users share their own information. We propose a trust-based model to assess the risk of sharing sensitive information and use it in the proposed algorithm. Moreover, we prove that the algorithm could be solved in polynomial time. Our results rely heavily on adopting the super modularity property of the risk function, which allows us to employ techniques from convex optimization. To evaluate our model, we conduct a user study to collect demographic information of several social networks users and get their perceptions on risk and trust. In addition, through experimental studies on synthetic data, we compare our proposed algorithm with the optimal algorithm both in terms of risk and time. We show that the proposed algorithm is scalable and that the sacrifice in risk is outweighed by the gain in efficiency.

关键词： Social network services Access control Data models Kernel Information management Electronic mail Privacy

来源：评论

学校读者我要写书评

暂无评论

Two Proofs for Shallow Packings 31

Two Proofs for Shallow Packings

引用

31st International Symposium on Computational Geometry, SoCG 2015

作者： Dutta, Kunal Ezra, Esther Ghosh, Arijit D1: Algorithms and Complexity Max-Planck-Institut für Informatik Saarbrücken66123 Germany Department of Computer Science and Engineering Polytechnic Institute of NYU BrooklynNY11201-3840 United States School of Mathematics Georgia Institute of Technology AtlantaGA30332 United States

ISBN: (纸本)9783939897835

We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X;we view V as a set of indicator vectors over the n-dimensional unit cube. A δ-separated set of V is a subcollection W, s.t. The Hamming distance between each pair u, v 2 W is greater than δ, where δ > 0 is an integer parameter. The δ-packing number is then defined as the cardinality of the largest δ-separated subcollection of V. Haussler showed an asymptotically tight bound of φ((n/δ)d) on the δ-packing number if V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X′ ⊆ X of size m ≤ n and for any parameter 1 ≤ κ ≤ m, the number of vectors of length at most κ in the restriction of V to X′ is only O(md1kd-d1 ), for a fixed integer d > 0 and a real parameter 1 ≤ d1 ≤ d (this generalizes the standard notion of bounded primal shatter dimension when d1 = d). In this case when V is "κ-shallow" (all vector lengths are at most κ), we show that its δ-packing number is O(nd1kd-d1/δd), matching Haussler s bound for the special cases where d1 = d or κ = n. We present two proofs, the first is an extension of Haussler s approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler s proof.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Efficient Broadcast on Random Geometric Graphs 10

Efficient Broadcast on Random Geometric Graphs

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Milan Bradonjic Robert Elsaesser Tobias Friedrich Thomas Sauerwald Alexandre Stauffer Theoretical Division and Center for Nonlinear Studies Los Alamos National Laboratory Department of Computer Science University of Paderborn Department 1: Algorithms and Complexity School of Computing Science Simon Fraser University Computer Science Division University of California

ISBN: (纸本)9780898717013

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing n nodes independently and uniformly at random in [0, {the square root of}n]~2 and creating edges between every pair of nodes having Euclidean distance at most r, for some prescribed r. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability 1 - O(n~(-1)) this algorithm informs every node in the largest connected component of an RGG within O({the square root of}n/r＋log n) rounds. This holds for any value of r larger than the critical value for the emergence of a connected component with Ω(n) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in [0, {the square root of}n]~2, the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is {direct}({the square root of}/r), which surprisingly has been an open problem so far.

关键词： connected component Square root Random Ganglia Line of nodes shortest path Euclidean distance

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共1页 << < 1 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：