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

Computing exact clustering posteriors with subset convolution

COMMUNICATIONS IN STATISTICS-THEORY AND METHODS 2016年第10期45卷 3048-3058页

作者： Kohonen, Jukka Corander, Jukka Univ Helsinki Dept Math & Stat POB 68 FI-00014 Helsinki Finland

An exponential-time exact algorithm is provided for the task of clustering n items of data into k clusters. Instead of seeking one partition, posterior probabilities are computed for summary statistics: the number of clusters and pairwise co-occurrence. The method is based on subset convolution and yields the posterior distribution for the number of clusters in O(n3(n)) operations or O(n(3)2(n)) using fast subset convolution. Pairwise co-occurrence probabilities are then obtained in O(n(3)2(n)) operations. This is considerably faster than exhaustive enumeration of all partitions.

关键词： Clustering exact algorithms Subset convolution 62H30 62F15 11B13

来源：评论

学校读者我要写书评

暂无评论

Optimal placement of multiple types of detectors under a small vessel attack threat to port security

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2016年 93卷 71-94页

作者： Yan, Xihong Nie, Xiaofeng Taiyuan Normal Univ Higher Educ Key Lab Engn & Sci Comp Taiyuan 030012 Peoples R China Nanyang Technol Univ Sch Mech & Aerosp Engn Singapore 639798 Singapore

We focus on a threat scenario where a terrorist would utilize a small vessel to attack a maritime target. We consider how to place multiple types of detectors to protect maritime targets from such an attack. Detectors are not perfectly reliable. The resulting detector placement problem is formulated as a nonlinear binary integer program such that the expected damage cost caused by the small vessel attack is minimized. Two exact algorithms and a greedy adding heuristic are proposed. Moreover, we conduct a detailed computational study and provide a case study in New York Harbor. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Port security Small vessel attack Detector deployment exact algorithms

来源：评论

学校读者我要写书评

暂无评论

H-index manipulation by merging articles: Models, theory, and experiments

引用

ARTIFICIAL INTELLIGENCE 2016年第0期240卷 19-35页

作者： van Bevern, Rene Komusiewicz, Christian Niedermeier, Rolf Sorge, Manuel Walsh, Toby Novosibirsk State Univ Ul Pirogova 2 Novosibirsk 630090 Russia Russian Acad Sci Siberian Branch Sobolev Inst Math Novosibirsk Russia Univ Jena Inst Informat D-07745 Jena Germany TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ New South Wales Sydney NSW Australia Data61 Sydney NSW Australia

An author's profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles;this may affect the H-index. We analyze the (parameterized) computational complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatibility graph whose edges correspond to plausible merges. Moreover, we consider several different measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles (that is, for compatibility graphs that are cliques), then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only if one merges articles with highly dissimilar titles. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Citation index Hirsch index Parameterized complexity exact algorithms AI's 10 to watch

来源：评论

学校读者我要写书评

暂无评论

BOUNDING THE RUNNING TIME OF algorithms FOR SCHEDULING AND PACKING PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第1期30卷 343-366页

作者： Jansen, K. Land, F. Land, K. Univ Kiel Inst Informat Olshausenstr 40 D-24098 Kiel Germany

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2(o(n)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), where vertical bar vertical bar I vertical bar vertical bar denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, < P2 vertical bar vertical bar C-max >, and < P2 vertical bar vertical bar Sigma w(j)C(j)>. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x vertical bar vertical bar I vertical bar vertical bar(O(n)). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)) and n(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), respectively.

关键词： scheduling packing exponential time hypothesis exact algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Shortest color-spanning intervals

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part3期609卷 561-568页

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

引用

JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS 2016年第2期32卷 175-196页

作者： Nagamani, A. N. Ashwin, S. Abhishek, B. Agrawal, V. K. PES Inst Technol Dept ECE PES Univ Campus Bangalore Karnataka India PES Inst Technol Dept Informat Sci & Engn PES Univ Campus Bangalore Karnataka India

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS's indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.

关键词： exact algorithms Testing Redundant faults Stuck-at faults Missing gate faults

来源：评论

学校读者我要写书评

暂无评论

Extending Lifetime Through Partial Coverage And Roles Allocation in Connectivity-Constrained Sensor Networks

引用

IFAC-PapersOnLine 2016年第12期49卷 973-978页

作者： Carrabs, Francesco Cerulli, Raffaele D'Ambrosio, Ciriaco Raiconi, Andrea Department of Mathematics University of Salerno Via Giovanni Paolo II 132 Fisciano84084 Italy

We consider a scenario in which certain target locations are monitored through sensors, which are scattered all over a considered area. A quality-of-service threshold imposes that, at any given time, a predefined percentage of the overall number of targets must be monitored. Furthermore, the activated sensors must be able to transmit the sensed information to a central base station, and the different roles assumed by the sensors (sensing, relay or idle) lead to different energy consumptions. We propose an exact algorithm to solve the problem of maximizing the operational time in this scenario, and test it on a set of benchmark instances. © 2016

关键词： Sensor networks Benchmarking Genetic algorithms Linear programming Quality of service Sensors Telecommunication networks Column generation Constrained sensors exact algorithms Maximum lifetimes Partial coverage Roles Allocation Target location

来源：评论

学校读者我要写书评

暂无评论

Dominating set based exact algorithms for 3-coloring

引用

INFORMATION PROCESSING LETTERS 2011年第6期111卷 251-255页

作者： Narayanaswamy, N. S. Subramanian, C. R. Inst Math Sci Madras 600113 Tamil Nadu India IIT Madras Dept CSE Madras Tamil Nadu India

We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2(o(n)) time for graphs having minimum degree at least w(n) where w(n) is any function which goes to infinity. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2(o(n)) time nor a 2(o(m)) time algorithm is possible (m denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(1.2535(n)) time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Design of algorithms Graph coloring 3-coloring exact algorithms Exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving Rank-Constrained Semidefinite Programs in exact Arithmetic 16

Solving Rank-Constrained Semidefinite Programs in Exact Arit...

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Naldi, Simone Fields Inst Res Math Sci 222 Coll St Toronto ON M5T 3J1 Canada

ISBN: (纸本)9781450343800

We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix is fixed, the complexity is polynomial in the number of variables. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We also implement it in Maple and discuss practical experiments.

关键词： Semidefinite programming LMI rank constraints exact algorithms polynomial optimization spectrahedra sums of squares

来源：评论

学校读者我要写书评

暂无评论

Color Spanning Objects: algorithms and Hardness Results 2nd

Color Spanning Objects: Algorithms and Hardness Results

引用

2nd International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Banerjee, Sandip Misra, Neeldhara Nandy, Subhas C. Indian Stat Inst Kolkata India Indian Inst Technol Gandhinagar India

ISBN: (纸本)9783319292212;9783319292205

In this paper, we study the Shortest Color Spanning Intervals problem, and related generalizations, namely Smallest Color Spanning t Squares and Smallest Color Spanning t Circles. The generic setting is the following: we are given n points in the plane (or on the line), each colored with one of k colors, and for each color i we also have a demand si. Given a budget t, we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least si points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors.

关键词： Color spanning sets Computational geometry Parameterized complexity exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：