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

quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs

THEORETICAL COMPUTER SCIENCE 2022年 902卷 64-75页

作者： Elbassioni, Khaled Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates

A hypergraph 7-t on n vertices and m edges is said to be nearly-intersecting if every edge of 7-t intersects all but at most polylogarthmically many (in m and n) other edges. Given lists of colors G(v), for each vertex v is an element of V, 7-t is said to be G-(list) colorable, if each vertex can be assigned a color from its list such that no edge in 7-t is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in m and n. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Hypergraph coloring Hypergraph dualization Exact algorithms quasi-polynomial algorithm List coloring

来源：评论

学校读者我要写书评

暂无评论

Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

引用

AUTOMATICA 2017年 76卷 153-163页

作者： Etesami, Seyed Rasoul Basar, Tamer Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n(2+lnD)), where n is the number of players and D is the diameter of the network, which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy Nash equilibrium (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Capacitated selfish replication game Pure Nash equilibrium (NE) Potential function quasi-polynomial algorithm Price of anarchy Optimal allocation

来源：评论

学校读者我要写书评

暂无评论

COMPUTATION OF A 30750-BIT BINARY FIELD DISCRETE LOGARITHM

引用

MATHEMATICS OF COMPUTATION 2021年第332期90卷 2997-3022页

作者： Granger, Robert Kleinjung, Thorsten Lenstra, Arjen K. Wesolowski, Benjamin Zumbraegel, Jens Univ Surrey Surrey Ctr Cyber Secur Dept Comp Sci Guildford Surrey England Ecole Polytech Fed Lausanne Lab Cryptol Algorithms Sch Comp & Commun Sci Lausanne Switzerland Univ Bordeaux CNRS Bordeaux INP IMBUMR 5251 F-33400 Talence France Univ Passau Fac Comp Sci & Math Passau Germany

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbragel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about 2900 core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately 3100 core years expended for the discrete logarithm record for prime fields, set in a field of bit-length 795, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Grobner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the L(1/4 + o(1)) complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.

关键词： Discrete logarithm problem finite fields binary fields quasi-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An Approximation algorithm and Price of Anarchy for the Binary-Preference Capacitated Selfish Replication Game 54

An Approximation Algorithm and Price of Anarchy for the Bina...

引用

54th IEEE Conference on Decision and Control (CDC)

作者： Etesami, Seyed Rasoul Basar, Tamer Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

ISBN: (纸本)9781479978861

We consider in this paper a simple model for human interactions as service providers of different resources over social networks, and study the dynamics of selfish behavior of such social entities using a game-theoretic model known as binary-preference capacitated selfish replication (CSR) game. It is known that such games have an associated ordinal potential function, and hence always admit a pure-strategy Nash equilibrium (NE). We study the price of anarchy of such games, and show that it is bounded above by 3;we further provide some instances for which the price of anarchy is at least 2. We also devise a quasi-polynomial algorithm O(n(2+ln D)) which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy Nash equilibrium of the game, where the parameters n, and D denote, respectively, the number of players, and the diameter of the network. We further show that when the underlying network has a tree structure, every globally optimal allocation is a Nash equilibrium, which can be reached in only linear time.

关键词： Capacitated selfish replication game pure Nash equilibrium (NE) potential function quasi-polynomial algorithm price of anarchy optimal allocation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：