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

Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications

ALGORITHMICA 2012年第1期64卷 3-18页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances A. Max Plank Inst Informat D-66123 Saarbrucken Germany Charles Darwin Univ Sch Engn & Informat Technol Darwin NT 0909 Australia

We show that three subclasses of bounded treewidth graphs are well quasi ordered by refinements of the minor order. Specifically, we prove that graphs with bounded vertex cover are well quasi ordered by the induced subgraph order, graphs with bounded feedback vertex set are well quasi ordered by the topological-minor order, and graphs with bounded circumference are well quasi ordered by the induced minor order. Our results give algorithms for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.

关键词： Well quasi order Treewidth Tree decomposition Bounded vertex cover graphs Bounded feedback vertex set graphs Bounded circumference graphs Parameterized complexity exact algorithms Meta-algorithms Geometric graph recognition String graphs

来源：评论

学校读者我要写书评

暂无评论

Matchings under Preferences: Strength of Stability and Trade-Offs 19

Matchings under Preferences: Strength of Stability and Trade...

引用

20th ACM Conference on Economics and Computation (ACM EC) held as part of the ACM Federated Computing Research Conference

作者： Chen, Jiehua Skowron, Piotr Sorge, Manuel Univ Warsaw Warsaw Poland

ISBN: (纸本)9781450367929

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classic definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classic sense, even if the agents slightly change their preferences. Near stability, on the other hand, imposes that a matching must become stable (again, in the classic sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative;together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of trade-offs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined trade-offs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching, and we prove that finding a socially optimal and nearly stable matching is computationally hard.

关键词： Stable matchings concepts of stability NP-hardness parameterized complexity analysis exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for optimal 2-constraint satisfaction and its implications

引用

THEORETICAL COMPUTER SCIENCE 2005年第2-3期348卷 357-365页

作者： Williams, R Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm. More precisely, the runtime bound is a constant factor improvement in the base of the exponent: the algorithm can count the number of optima in MAX-2-SAT and MAX-CUT instances in O(m(3)2(omega n/3)) time, where omega < 2.376 is the matrix product exponent over a ring. When the constraints have arbitrary weights, there is a (1 + epsilon)-approximation with roughly the same runtime, modulo polynomial factors. Our construction shows that improvement in the runtime exponent of either k-clique solution (even when k = 3) or matrix multiplication over G F(2) would improve the runtime exponent for solving 2-CSP optimization. Our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter of n points in l(1), then there is an (2 - epsilon)(n) algorithm for MAX-LIN. These results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems. (c) 2005 Elsevier B.V. All rights reserved.

关键词： exact algorithms constraint satisfaction MAX-2-SAT MAX-CUT

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for MIN INDEPENDENT DOMINATING SET

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 558-572页

作者： Bourgeois, N. Della Croce, F. Escoffier, B. Paschos, V. Th. CNRS LAMSADE F-75700 Paris France Univ Paris 09 F-75775 Paris 16 France Politecn Torino DAI Turin Italy

We first devise a branching algorithm that computes a minimum independent dominating set with running time O*(1.3351(n)) = O*(2(0.417n)) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1 + epsilon, for any epsilon > 0, in a time smaller than the one of exact computation and exponentially decreasing with epsilon. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se. (C) 2012 Elsevier B.V. All rights reserved.

关键词： MIN INDEPENDENT DOMINATING SET Exponential algorithms exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On explaining integer vectors by few homogeneous segments

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 766-782页

作者： Bredereck, Robert Chen, Jiehua Hartung, Sepp Komusiewicz, Christian Niedermeier, Rolf Suchy, Ondrej TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

We extend previous studies on "explaining" a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete variants which are motivated by radiation therapy and database applications. In VECTOR POSITIVE EXPLANATION, the segments may have only positive integer entries;in VECTOR EXPLANATION, the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry y and the maximum difference 8 between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that VEcrox EXPLANATION is fixed-parameter tractable with respect to delta, and that, unless NP subset of coNP/poly, there is no polynomial kernelization for VECTOR POSITIVE EXPLANATION with respect to the parameter gamma. We also identify relevant special cases where VECTOR POSITIVE EXPLANATION is algorithmically harder than VECTOR EXPLANATION. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Parameterized complexity Matrix and vector decomposition Multivariate algorithmics NP-hardness exact algorithms

来源：评论

学校读者我要写书评

暂无评论

On the minimum corridor connection problem and other generalized geometric problems

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2009年第9期42卷 939-951页

作者： Bodlaender, Hans L. Feremans, Corinne Grigoriev, Alexander Penninkx, Eelko Sitters, Rene Wolle, Thomas Maastricht Univ Dept Quantitat Econ NL-6200 MD Maastricht Netherlands Univ Utrecht Inst Informat & Comp Sci NL-3508 TB Utrecht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands NICTA Sydney Alexandria NSW 1435 Australia

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum corridor connection Generalized geometric problems Complexity exact algorithms Approximations

来源：评论

学校读者我要写书评

暂无评论

Optimization of packet scheduling in wireless systems with smart antennas: geometric models and algorithms

Optimization of packet scheduling in wireless systems with s...

引用

IEEE International Conference on Communications (ICC 2004)

作者： Amaldi, E Capone, A Malucelli, F Villa, G Politecn Milan DEI I-20133 Milan Italy

ISBN: (纸本)0780385330

Beam forming techniques of adaptive antenna arrays (smart antennas) allow to reduce the mutual interference of simultaneous transmission in wireless access systems exploiting angular separation of user terminals. At the radio resource management layer the information on the arrival direction of signals can be taken into account by the scheduling algorithm so that transmissions of too close user terminals can be scheduled in different time-slots, while transmissions of users with an enough angular separation can be simultaneous. In other words, time diversity is exploited by the scheduling algorithm when spatial diversity is not sufficient to obtain good quality transmissions. In this paper we propose a novel approach to the problem of packet scheduling with smart antennas using mathematical programming. Based on a simplified system model we formulate two combinatorial optimization problems. In the first problem we have to select a subset of users which can be simultaneously served in a given time slot so as to maximize the number or the total priority of the users served. An arc-circular model is proposed together with an exact polynomial-time algorithm which searches for a path of maximum total weight in an appropriate graph. In the second problem users must be partitioned into non-interfering subsets so as to minimize the number of time slots needed to transmit all the given packets. For both problems heuristics have been devised in order to obtain approximate solutions in the short time available for packet scheduling in real systems.

关键词： packet scheduling smart antennas SDMA cross-layer optimization radio resource management exact algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

Solving connectivity problems parameterized by treewidth in single exponential time (Extended abstract)

Solving connectivity problems parameterized by treewidth in ...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Cygan, Marek Nederlof, Jesper Pilipczuk, Marcin Pilipczuk, Michal van Rooij, Johan M. M. Wojtaszczyk, Jakub Onufry Univ Warsaw Inst Informat Warsaw Poland Univ Bergen Dept Informat Bergen Norway Univ Warsaw Fac Math Fac Informat Fac Mech Warsaw Poland Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Google Inc Krakow Poland

ISBN: (纸本)9780769545714

For the vast majority of local problems on graphs of small treewidth (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c(tw) vertical bar V vertical bar(O(1)) time algorithms, where tw is the treewidth of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in at least tw(tw) time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c(tw) vertical bar V vertical bar(O(1)) time Monte Carlo algorithms for most connectivity-type problems, including HAMILTONIAN PATH, STEINER TREE, FEEDBACK VERTEX SET and CONNECTED DOMINATING SET. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like CYCLE PACKING.

关键词： treewidth fixed parameter tractability randomized algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT 12th

Upper and Lower Bounds for Different Parameterizations of (n...

引用

12th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Belova, Tatiana Bliznets, Ivan Russian Acad Sci St Petersburg Dept Steklov Inst Math St Petersburg Russia

ISBN: (纸本)9783030046514;9783030046507

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem.

关键词： Maximum satisfiability exact algorithms Parameterization above guarantee

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for optimal 2-constraint satisfaction and its implications

A new algorithm for optimal 2-constraint satisfaction and it...

引用

31st International Colloquium on Automata, Languages and Programming (ICALP 2004)

作者： Williams, R Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA

关键词： exact algorithms constraint satisfaction MAX-2-SAT MAX-CUT

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：