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

Exact bounds for distributed graph colouring 1

22nd International Colloquium on Structural Information and Communication complexity, SIROCCO 2015

作者： Rybicki, Joel Suomela, Jukka Helsinki Institute for Information Technology HIIT Department of Computer Science Aalto University Saarbrücken Finland Department of Algorithms and Complexity Max Planck Institute for Informatics Saarbrücken Germany

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring (Formula presented.)in communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely (Formula presented.) communication rounds. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Computing Teichmüller Maps between Polygons 31

Computing Teichmüller Maps between Polygons

引用

31st International Symposium on Computational Geometry, SoCG 2015

作者： Goswami, Mayank Gu, Xianfeng Pingali, Vamsi P. Telang, Gaurish Algorithms and Complexity Max-Planck Institute for Informatics Saarbrücken66123 Germany Department of Computer Science Stony Brook University Stony BrookNY11794-4400 United States Department of Mathematics Johns Hopkins University BaltimoreMD21218 United States Department of Applied Mathematics and Statistics Stony Brook University Stony BrookNY11794-3600 United States

ISBN: (纸本)9783939897835

By the Riemann mapping theorem, one can bijectively map the interior of an n-gon P to that of another n-gon Q conformally (i.e., in an angle preserving manner). However, when this map is extended to the boundary it need not necessarily map the vertices of P to those of Q. For many applications it is important to find the "best" vertex-preserving mapping between two polygons, i.e., one that minimizes the maximum angle distortion (the so-called dilatation). Such maps exist, are unique, and are known as extremal quasiconformal maps or Teichmüller maps. There are many efficient ways to approximate conformal maps, and the recent breakthrough result by Bishop computes a (1+Ε)-approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps. We present two results in this paper. One studies the problem in the continuous setting and another in the discrete setting. In the continuous setting, we solve the problem of finding a finite time procedure for approximating Teichmüller maps. Our construction is via an iterative procedure that is proven to converge in O(poly(1/Ε)) iterations to a (1 + Ε)-approximation of the Teichmüller map. Our method uses a reduction of the polygon mapping problem to the marked sphere problem, thus solving a more general problem. In the discrete setting, we reduce the problem of finding an approximation algorithm for computing Teichmüller maps to two basic subroutines, namely, computing discrete 1) compositions and 2) inverses of discretely represented quasiconformal maps. Assuming finite-time solvers for these subroutines we provide a (1 + Ε)-approximation algorithm.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Many-to-one boundary labeling with backbones

引用

Journal of Graph algorithms and Applications 2015年第3期19卷 779-816页

作者： Bekos, Michael A. Cornelsen, Sabine Fink, Martin Hong, Seok-Hee Kaufmann, Michael Nollenburg, Martin Rutter, Ignaz Symvonis, Antonios Institute for Informatics University of Tubingen Germany Department of Computer and Information Science University of Konstanz Germany Department of Computer Science UC Santa Barbara United States School of Information Technologies University of Sydney Australia Algorithms and Complexity Group TU Wien Vienna Austria Institute of Theoretical Informatics KIT Karlsruhe Germany School of Applied Mathematics and Physical Sciences NTUA Greece

We study a boundary labeling problem, where multiple points may connect to the same label. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points that need to be connected to this label are linked via vertical line segments to the backbone. We present dynamic programming algorithms for minimizing the total number of label occurrences and for minimizing the total leader length of crossing-free backbone labelings. When crossings are allowed, we aim at obtaining solutions with the minimum number of crossings. This can be achieved efficiently in the case of fixed label order;however, in the case of flexible label order we show that minimizing the number of leader crossings is NP-hard. © 2015, Brown University. All right reserved.

关键词： Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Epistemic ATL with perfect recall, past and strategy contexts

Epistemic ATL with perfect recall, past and strategy context...

引用

13th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA XIII

作者： Guelev, Dimitar P. Dima, Catalin Institute of Mathematics and Informatics Bulgarian Academy of Sciences Belgium Laboratory of Algorithms Complexity and Logic Université Paris Est-Créteil France

We propose an extension to epistemic ATL with perfect recall, past, and distributed knowledge by strategy contexts and demonstrate the strong completeness of a Hilbert-style proof system for its (. .)-free subset. ... 详细信息

ISBN: (纸本)9783642328961

关键词： Computers

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Foundations of evolutionary multi-objective optimization 11

Foundations of evolutionary multi-objective optimization

引用

13th Annual Genetic and Evolutionary Computation Conference - Companion Publication, GECCO 2011 Companion

作者： Friedrich, Tobias Neumann, Frank Algorithms and Complexity Max Planck Institute for Informatics Germany School of Computer Science University of Adelaide Australia

来源：评论

学校读者我要写书评

暂无评论

Optimizing the layout of 1000 wind turbines

Optimizing the layout of 1000 wind turbines

引用

European Wind Energy Conference and Exhibition 2011, EWEC 2011

作者： Wagner, Markus Veeramachaneni, Kalyan Neumann, Frank O'Reilly, Una-May Algorithms and Complexity Max Planck Institute for Informatics Germany Massachusetts Institute of Technology CSAIL United States School of Computer Science University of Adelaide Australia

ISBN: (纸本)9781618399915

In this paper we demonstrate an accurate, efficient, and parallelizable optimization algorithm for the layout of hundreds, then 1000, turbines. It is modular and therefore allows different wake effect models to be incorporated. Its computational cost is a relation which depends upon how many candidate layouts it investigates and the complexity of its wake loss calculation. We demonstrate how well it maximizes energy capture and show how it allows one to examine how wake loss scales with energy capture and number of turbines. Keywords: Wind farm design, output maximization, wake consideration, Covariance Matrix Adaptation, Evolutionary strategy.

关键词： Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs 11

Coloring random graphs online without creating monochromatic...

引用

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

作者： Torsten Mutze Thomas Rast Reto Spohel Institute of Theoretical Computer Science Algorithms and Complexity Group

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph G_(n,p) on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of G_(n,p) are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r≥2 this problem has a threshold p0(F, r, n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of G_(n,p) that is valid w.r.t. F online, and for any function p(n)=ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic twoplayer game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a valueγ=γ(F,r) such that the threshold of the probabilistic problem is given by p0(F, r, n) = n~(-γ). Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of G_(n,p) online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n~(-γ)).

关键词： Color Fluorine (F) vertex head Valid AASS gene colored graph Line graph Probability Stochastic Processes

来源：评论

学校读者我要写书评

暂无评论

On Balanced Coloring Games in Random Graphs

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 425-430页

作者： Gugelmann, Luca Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

Consider the balanced Ramsey game, in which a player has r colors and where in each round r random edges of an initially empty graph on n vertices are presented. The player has to immediately assign a different color to each edge and her goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. The Achlioptas game is similar, but the player only loses when she creates a copy of F in one distinguished color. We show that there is an infinite family of nonforests F for which the balanced Ramsey game has a different threshold than the Achlioptas game, settling an open question by Krivelevich et al. We also consider the natural vertex analogues of both games and show that their thresholds coincide for all graphs F, in contrast to our results for the edge case. © 2011 Elsevier B.V.

关键词： Coloring games Ramsey theory Random graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：