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

THEORY OF COMPUTING SYSTEMS 2017年第2期60卷 253-279页

作者： Bulteau, Laurent Fafianie, Stefan Froese, Vincent Niedermeier, Rolf Talmon, Nimrod Univ Paris Est Marne La Vallee CNRS UMR 8049 IGM LabInfo Marne La Vallee France Univ Bonn Inst Informat Bonn Germany Weizmann Inst Sci Rehovot Israel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of "effector nodes";these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of Effectors, identifying both tractable and intractable cases. To this end, we also exploit a parameterization measuring the "degree of randomness" (the number of 'really' probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.

关键词： Probabilistic information propagation Influence maximization etwork activation Social networks exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A short note on Merlin-Arthur protocols for subset sum

引用

INFORMATION PROCESSING LETTERS 2017年第Feb.期118卷 15-16页

作者： Nederlof, Jesper Tech Univ Eindhoven Dept Math & Comp Sci Eindhoven Netherlands

Given n positive integers we show how to construct a proof that the number of subsets summing to a particular integer t equals a claimed quantity. The proof is of size 0*(root t), can be constructed in 0*(t) time and can be probabilistically verified in time 0*(root t) with at most 1/2 one-sided error probability. Here 0*(.) omits factors polynomial in the input size. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Subset sum Probabilistic verification exact algorithms Merlin-Arthur protocol Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Tramp ship routing and scheduling with voyage separation requirements

引用

OR SPECTRUM 2017年第4期39卷 913-943页

作者： Vilhelmsen, Charlotte Lusby, Richard M. Larsen, Jesper Tech Univ Denmark Dept Engn Management Prod TorvetBldg 426 DK-2800 Lyngby Denmark

In this paper we explore tramp ship routing and scheduling. Tramp ships operate much like taxies following the available demand. Tramp operators can determine some of their demand in advance by entering into long-term contracts and then try to maximise profits from optional voyages found in the spot market. Routing and scheduling a tramp fleet to best utilise fleet capacity according to current demand is therefore an ongoing and complicated problem. Here we add further complexity to the routing and scheduling problem by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. The incorporation of these separation requirements helps balance the conflicting objectives of maximising profit for the tramp operator and minimising inventory costs for the charterer, since these costs increase if similar voyages are not performed with some separation in time. We have developed a new and exact branch-and-price procedure for this problem. We use a dynamic programming algorithm to generate columns and describe a time window branching scheme used to enforce the voyage separation requirements which we relax in the master problem. Computational results show that our algorithm in general finds optimal solutions very quickly and performs much faster compared to an earlier a priori path generation method. Finally, we compare our method to an earlier adaptive large neighbourhood search heuristic and find that on similar-sized instances our approach generally uses less time to find the optimal solution than the adaptive large neighbourhood search method uses to find a heuristic solution.

关键词： Scheduling Maritime transport Spread requirement Optimization exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A bi-objective network design approach for discovering functional modules linking Golgi apparatus fragmentation and neuronal death

引用

ANNALS OF OPERATIONS RESEARCH 2017年第1期258卷 5-30页

作者： Alvarez-Miranda, Eduardo Farhan, Hesso Luipersbeck, Martin Sinnl, Markus Univ Talca Dept Ind Engn Curico Chile Biotechnol Inst Thurgau Kreuzlingen Switzerland Univ Konstanz Dept Biol Constance Germany Univ Vienna Dept Stat & Operat Res Fac Business Econ & Stat Vienna Austria

Experimental records show the existence of a biological linkage between neuronal death and Golgi apparatus fragmentation. The comprehension of such linkage should help to understand the dynamics undergoing neurological damage caused by diseases such as Alzheimer's disease or amyotrophic lateral sclerosis. In this paper, the bi-objective minimum cardinality bottleneck Steiner tree problem along with an ad-hoc exact algorithm are proposed to study such phenomena. The proposed algorithm is based on integer programming and the so-called -constraint method. A key feature of the devised approach is that it allows an efficient integer programming formulation of the problem. The obtained results show that it is possible to obtain additional evidence supporting the hypothesis that alterations of the Golgi apparatus structure and neuronal death interact through the biological mechanisms underlying the outbreak and progression of neurodegenerative diseases. Moreover, the function of cellular response to stress as a biological linkage between these phenomena is also further investigated. Complementary, computational results on a synthetic dataset are also provided with the aim of reporting the performance of the proposed algorithm.

关键词： Neuroscience Neurodegeneration Steiner tree exact algorithms Bi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

Optimization algorithms for Clique Problems

Optimization Algorithms for Clique Problems

引用

作者： Yi Zhou UNIVERSITE D'ANGERS Label europeen

学位级别：博士

This thesis considers four clique problems: the maximum vertex weight clique problem (MVWCP), the maximum s-plex problem (MsPlex), the maximum balanced biclique problem (MBBP) and the clique partitioning problem (CPP). The first three are generalization and relaxation of the classic maximum clique problem (MCP), while the last problem belongs to a clique grouping problem. These combinatorial problems have numerous practical applications. Given that they all belong to the NP-Hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to develop effective algorithms to tackle these challenging problems. Specifically, we propose two restart tabu search algorithms based on a generalized PUSH operator for MVWCP, a frequency driven local search algorithms for MsPlex, a graph reduction based tabu search as well as effective exact branch and bound algorithms for MBBP and lastly, a three phase local search algorithm for CPP. In addition to the design of efficient move operators for local search algorithms, we also integrate components like graph reduction or upper bound propagation in order to deal deal with very large real-life networks. The experimental tests on a wide range of instances show that our algorithms compete favorably with the main state-of-the-art algorithms.

关键词： Clique problems Local search Large real-life networks Metaheuristics exact algorithms Computational experiments

来源：评论

学校读者我要写书评

暂无评论

On exact algorithms for Treewidth

引用

ACM TRANSACTIONS ON algorithms 2012年第1期9卷 12-12页

作者： Bodlaender, Hans L. Fomin, Fedor V. Koster, Arie M. C. A. Kratsch, Dieter Thilikos, Dimitrios M. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Univ Aachen Aachen Germany Univ Metz LITA F-507045 Metz 01 France Univ Athens GR-10679 Athens Greece

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2(n)). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the TRAVELING SALESMAN problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing TREEWIDTH under the restriction that the space used is only polynomial and give a simple O*(4(n)) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, TREEWIDTH can be computed in O*(2.9512(n)) time and polynomial space.

关键词： algorithms Design Theory Experimentation Graph algorithms exact algorithms treewidth dynamic programming separators

来源：评论

学校读者我要写书评

暂无评论

A note on exact and heuristic algorithms for the identical parallel machine scheduling problem

引用

JOURNAL OF HEURISTICS 2012年第6期18卷 939-942页

作者： Dell'Amico, Mauro Iori, Manuel Martello, Silvano Monaci, Michele Univ Bologna DEIS I-40136 Bologna Italy Univ Modena & Reggio Emilia DISMI I-42122 Reggio Emilia Italy Univ Padua DEI I-35131 Padua Italy

A recent paper (Davidovic et al., J. Heuristics, 18:549-569, 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution.

关键词： Identical parallel machine scheduling exact algorithms Metaheuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for dominating set

引用

DISCRETE APPLIED MATHEMATICS 2011年第17期159卷 2147-2164页

作者： van Rooij, Johan M. M. Bodlaender, Hans L. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like DOMINATING SET and INDEPENDENT SET. This approach is used in this paper to obtain a faster exact algorithm for DOMINATING SET. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969(n)) time and polynomial space algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： exact algorithms Exponential time algorithms Branch and reduce Measure and conquer Dominating set Computer aided algorithm design

来源：评论

学校读者我要写书评

暂无评论

exact and Approximation algorithms for Geometric and Capacitated Set Cover Problems

引用

ALGORITHMICA 2012年第2期64卷 295-310页

作者： Berman, Piotr Karpinski, Marek Lingas, Andrzej Lund Univ Dept Comp Sci S-22100 Lund Sweden Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Univ Bonn Dept Comp Sci Bonn Germany

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r+1.357. In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.

关键词： Set cover Geometric set cover Capacitated set cover Assignment of directional antenna Shipping with deadlines Approximation algorithms Polynomial-time approximation scheme APX-hardness exact algorithms Time complexity

来源：评论

学校读者我要写书评

暂无评论

The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)

引用

QUANTUM SCIENCE AND TECHNOLOGY 2017年第3期2卷

作者： Mandra, Salvatore Katzgraber, Helmut G. Thomas, Creighton NASA Ames Res Ctr Quantum Artificial Intelligence Lab Moffett Field CA 94035 USA Stinger & Ghaffarian Technol 7701 Greenbelt RdSuite 400 Greenbelt MD 20770 USA Texas A&M Univ Dept Phys & Astron College Stn TX 77843 USA 1QB Informat Technol Vancouver BC V6B 4W4 Canada Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Google Inc 111 8th Ave New York NY 10011 USA

In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.

关键词： quantum annealing spin glasses P versus NP exact algorithms benchmarking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：