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

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： de Berg, Mark Bodlaender, Hans L. Kisfaludi-Bak, Sandor Kolay, Sudeshna Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Univ Utrecht Dept Comp Sci Utrecht Netherlands

ISBN: (纸本)9781538642306

We study exact algorithms for EUCLIDEAN TSP in R-d. In the early 1990s algorithms with n(O)(root n) running time were presented for the planar case, and some years later an algorithm with n(O)(n(1-1/d)) running time was presented for any d >= 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on EUCLIDEAN TSP, except for a lower bound stating that the problem admits no 2(O)(n(1-1/d-epsilon)) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of EUCLIDEAN TSP by giving a 2(O(n1-1/d)) algorithm and by showing that a 2(o(n1-1/d)) algorithm does not exist unless ETH fails.

关键词： Euclidean TSP separator theorem subexponential algorithms ETH

来源：评论

学校读者我要写书评

暂无评论

A Framework for ETH-Tight algorithms and Lower Bounds in Geometric Intersection Graphs 2018

A Framework for ETH-Tight Algorithms and Lower Bounds in Geo...

引用

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

作者： de Berg, Mark Bodlaender, Hans L. Kisfaludi-Bak, Sandor Marx, Daniel van der Zanden, Tom C. Eindhoven Univ Technol Eindhoven Netherlands Univ Utrecht Utrecht Netherlands Eindhoven Univ Technol Utrecht Netherlands Hungarian Acad Sci MTA SZTAKI Budapest Hungary

ISBN: (纸本)9781450355599

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2(O(n1-1/d)) for any fixed dimension d >= 2 for many well known graph problems, including Independent Set, r -Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work;in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i. e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into d-dimensional grids, and it allows us to derive matching 2(Omega(n1-1/d)) lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.

关键词： Geometric intersection graphs subexponential algorithms Geometric separator Treewidth Graph minors

来源：评论

学校读者我要写书评

暂无评论

subexponential algorithms for partial cover problems

引用

INFORMATION PROCESSING LETTERS 2011年第16期111卷 814-818页

作者： Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif San Diego Dept CS & Engn San Diego CA 92103 USA

Partial Cover problems are optimization versions of fundamental and well-studied problems like VERTEX COVER and DOMINATING SET. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that PARTIAL VERTEX COVER and PARTIAL DOMINATING SET are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time 2(O(k))n(O(1)). During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical VERTEX COVER and DOMINATING SET problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for PARTIAL VERTEX COVER and PARTIAL DOMINATING SET. In this paper, we answer the question affirmatively by solving both problems in time 2(O(root k))n(O(1)) not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Parameterized algorithms subexponential algorithms Partial cover problems Partial Dominating Set

来源：评论

学校读者我要写书评

暂无评论

subexponential algorithms for Unique Games and Related Problems

Subexponential Algorithms for Unique Games and Related Probl...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Arora, Sanjeev Barak, Boaz Steurer, David Princeton Univ Dept Comp Sci CCI Princeton NJ 08544 USA Microsoft Res & Princeton Univ Princeton NJ 08544 USA Microsoft Res Cambridge MA USA

ISBN: (纸本)9780769542447

We give a subexponential time approximation algorithm for the UNIQUE GAMES problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, n(epsilon). The approximation guarantee depends on epsilon, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the UNIQUE GAMES. While our results stop short of refuting the UGC, they do suggest that UNIQUE GAMES is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, LABEL COVER and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every epsilon > 0 and every regular n -vertex graph G, by changing at most epsilon fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most n(epsilon) eigenvalues larger than 1 - eta, where eta depends polynomially on epsilon.

关键词： Approximation algorithms Unique Games subexponential algorithms Spectral Methods Eigenvalues Graph Decompositions Constraint Satisfaction Problems

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-905

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-905 by published by

关键词： algorithms bidimensional dominating dominating set euler genus feedback vertex fully dominated graph graphs minor bidimensional mit-lcs-tr-905 planar planar graph planar graphs running time set set problem subexponential algorithms theorem vertex vertices

来源：评论

学校读者我要写书评

暂无评论

subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

Subexponential Algorithm for <i>d</i>-Cluster Edge Deletion:...

引用

38th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Misra, Neeldhara Panolan, Fahad Saurabh, Saket Indian Inst Sci Bangalore 560012 Karnataka India Inst Math Sci Madras Tamil Nadu India

ISBN: (纸本)9783642403132;9783642403125

The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually "not too far apart", without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm [STACS, 2013]. That is, there is no algorithm solving the problem in time 2 degrees((k))n(O(1)). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time O(2(O(root dk)) + m + n). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2 degrees((k))n(O(1)). We show, further, that even the problem of deleting edges to obtain a graph with d s-clubs cannot be solved in time 2 degrees((k))n(O)(1) for any fixed s, d >= 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.

关键词： subexponential algorithms s-clubs cluster edge deletion ETH-hardness

来源：评论

学校读者我要写书评

暂无评论

TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2013年第1期24卷 3-14页

作者： Floderus, Peter Lingas, Andrzej Persson, Mia Lund Univ Ctr Math Sci S-22100 Lund Sweden Lund Univ Dept Comp Sci S-22100 Lund Sweden Malmo Univ Dept Comp Sci S-20506 Malmo Sweden

The firefighter problem models the situation where an infection, a computer virus, an idea or fire etc. is spreading through a network and the goal is to save as many as possible nodes of the network through targeted vaccinations. The number of nodes that can be vaccinated at a single time-step is typically one, or more generally O(1). In a nonstandard model, the so called spreading model, the vaccinations also spread in contrast to the standard model. Our main results are concerned with general graphs in the spreading model. We provide a very simple exact 2(O(root n log n))-time algorithm. In the special case of trees, where the standard and spreading model are equivalent, our algorithm is substantially simpler than that exact subexponential algorithm for trees presented in Ref. 2. On the other hand, we show that the firefighter problem on weighted directed graphs in the spreading model cannot be approximated within a constant factor better than 1 - 1/e unless NP subset of DTIME (n(O(log log n))) We also present several results in the standard model. We provide approximation algorithms for planar graphs in case when at least two vaccinations can be performed at a time-step. We also derive trade-offs between approximation factors for polynomial-time solutions and the time complexity of exact or nearly exact solutions for instances of the fireifighter problem for the so called directed layered graphs.

关键词： Approximation algorithms subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING

TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING

引用

17th Computing - The Australasian Theory Symposium (CATS) is part of the Australasian Computer Science Week (ACSW)

作者： Floderus, Peter Lingas, Andrzej Persson, Mia Lund Univ Ctr Math Sci S-22100 Lund Sweden Lund Univ Dept Comp Sci S-22100 Lund Sweden Malmo Univ Dept Comp Sci S-20506 Malmo Sweden

ISBN: (纸本)9781920682989

关键词： Approximation algorithms subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 417卷 95-107页

作者： Tazari, Siamak Humboldt Univ Dept Comp Sci D-10099 Berlin Germany

We improve the running time of the general algorithmic technique known as Baker's approach (1994) [1] on H-minor-free graphs from theta(n(integral(|H|))) to theta(integral(|H|)n(theta(1))). The numerous applications include, e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements. On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010) [20]. We use these algorithms to derive faster 2-approximations;furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique. We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes. We obtain as a corollary that all problems with a minor-monotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality. (C) 2011 Elsevier B.V. All rights reserved.

关键词： subexponential algorithms Graph minors Odd minors

来源：评论

学校读者我要写书评

暂无评论

Towards more efficient infection and fire fighting 2011

Towards more efficient infection and fire fighting

引用

Proceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 119

作者： Peter Floderu Andrzej Lingas Mia Persson Lund University Lund Sweden Malmö University Malmö Sweden

ISBN: (纸本)9781920682989

The firefighter problem models the situation where an infection, a computer virus, an idea or fire etc. is spreading through a network and the goal is to save as many as possible nodes of the network through targeted vaccinations. The number of nodes that can be vaccinated at a single time-step is typically one, or more generally O(1). In a non-standard model, the so called spreading model, the vaccinations also spread in contrast to the standard *** main results are concerned with general graphs in the spreading *** provide a very simple exact 2O(√n log n)-time algorithm. In the special case of trees, where the standard and spreading model are equivalent, our algorithm is substantially simpler than that exact subexponential algorithm for trees presented in (Cai et al. 2008). On the other hand, we show that the firefighter problem on weighted directed graphs in the spreading model cannot be approximated within a constant factor better than 1−1/e unless NP ⊆ DTIME(nO(log log n)).We also present several results in the standard model. We provide approximation algorithms for planar graphs in case when at least two vaccinations can be performed at a time-step. We also derive trade-offs between approximation factors for polynomial-time solutions and the time complexity of exact or nearly exact solutions for instances of the firefighter problem for the so called directed layered graphs.

关键词： approximation algorithms subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：