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

Two Kadane algorithms for the Maximum Sum Subarray Problem

algorithmS 2023年第11期16卷 519-519页

作者： Kadane, Joseph B. Carnegie Mellon Univ Dietrich Coll Humanities & Social Sci Dept Stat & Data Sci Pittsburgh PA 15213 USA

The maximum sum subarray problem is to find a contiguous subarray with the largest sum. The history of algorithms to address this problem is recounted, culminating in what is known as Kadane's algorithm. However, that algorithm is not the algorithm Kadane intended. Nonetheless, the algorithm known as Kadane's has found many uses, some of which are recounted here. The algorithm Kadane intended is reported here, and compared to the algorithm attributed to Kadane. They are both linear in time, employ just a few words of memory, and use a dynamic programming structure. The results proved here show that these two algorithms differ only in the case of an input consisting of only negative numbers. In that case, the algorithm Kadane intended is more informative than the algorithm attributed to him.

关键词： dynamic programming Kadane's algorithm linear algorithm maximum sum subarray problem

来源：评论

学校读者我要写书评

暂无评论

Core-Boosted linear Search for Incomplete MaxSAT 1

引用

16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Berg, Jeremias Demirovic, Emir Stuckey, Peter J. Univ Helsinki Dept Comp Sci HIIT Helsinki Finland Univ Melbourne Melbourne Vic Australia Monash Univ Melbourne Vic Australia CSIRO Data61 Canberra ACT Australia

ISBN: (数字)9783030192129

ISBN: (纸本)9783030192129;9783030192112

Maximum Satisfiability (MaxSAT), the optimisation extension of the well-known Boolean Satisfiability (SAT) problem, is a competitive approach for solving NP-hard problems encountered in various artificial intelligence and industrial domains. Due to its computational complexity, there is an inherent tradeoff between scalability and guarantee on solution quality in MaxSAT solving. Limitations on available computational resources in many practical applications motivate the development of complete any-time MaxSAT solvers, i.e. algorithms that compute optimal solutions while providing intermediate results. In this work, we propose core-boosted linear search, a generic search-strategy that combines two central approaches in modern MaxSAT solving, namely linear and core-guided algorithms. Our experimental evaluation on a prototype combining reimplementations of two state-of-the-art MaxSAT solvers, PMRES as the core-guided approach and LinSBPS as the linear algorithm, demonstrates that our core-boosted linear algorithm often outperforms its individual components and shows competitive and, on many domains, superior results when compared to other state-of-the-art solvers for incomplete MaxSAT solving.

关键词： Maximum Satisfiability MaxSAT SAT-based MaxSAT Incomplete solving linear algorithm Core-guided MaxSat

来源：评论

学校读者我要写书评

暂无评论

Lineární verze Holubova algoritmu

Lineární verze Holubova algoritmu

引用

作者： Tvrdý, David Charles University of Prague

This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a step-by-step visualization for particular input words. 1

关键词： morphic factorization fixed point linear algorithm

来源：评论

学校读者我要写书评

暂无评论

On computing secure domination of trees

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2021年第5期13卷

作者： Poureidi, Abolfazl Shahrood Univ Technol Fac Math Sci Shahrood Iran

Let G = (V,E) be a graph. A subset D subset of V is a dominating set of G if for each v is an element of V\D there is a vertex u is an element of D adjacent to v. A dominating set D of G is a secure dominating set of G if for each v is an element of V set minus D there is a vertex u is an element of D adjacent to v such that (D \{u}) boolean OR{v} is also a dominating set of G. The minimum cardinality of a secure dominating set of G is called the secure domination number of G. Burger et al. [A linear algorithm for secure domination in trees, Discrete Appl. Math. 171 (2014) 15-27] proposed a nontrivial algorithm for computing a minimum secure dominating set of a given tree in linear time and space. In this paper, we give a dynamic programming algorithm to compute the secure domination number of a given tree T = (V,E) in O(|V |) time and space and then using a backtracking search algorithm we can find a minimum secure dominating set of T in O(|V |) time and space that its implementation is much simpler than the implementation of the algorithm proposed by Burger et al.

关键词： Dominating set secure dominating set linear algorithm tree dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Satisfying Neighbor Preferences on a Circle 13th

Satisfying Neighbor Preferences on a Circle

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Krizanc, Danny Lafond, Manuel Narayanan, Lata Opatrny, Jaroslav Shende, Sunil Wesleyan Univ Dept Math & Comp Sci Middletown CT USA Univ Ottawa Dept Math & Stat Ottawa ON Canada Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada Rutgers State Univ Dept Comp Sci Camden NJ USA

ISBN: (纸本)9783319774046;9783319774039

We study the problem of satisfying seating preferences on a circle. We assume we are given a collection of n agents to be arranged on a circle. Each agent is colored either blue or red, and there are exactly b blue agents and r red agents. The w-neighborhood of an agent A is the sequence of 2w + 1 agents at distance <= w from A in the clockwise circular ordering. Agents have preferences for the colors of other agents in their w-neighborhood. We consider three ways in which agents can express their preferences: each agent can specify (1) a preference list: the sequence of colors of agents in the neighborhood, (2) a preference type: the exact number of neighbors of its own color in its neighborhood, or (3) a preference threshold: the minimum number of agents of its own color in its neighborhood. Our main result is that satisfying seating preferences is fixed-parameter tractable (FPT) with respect to parameter w for preference types and thresholds, while it can be solved in O(n) time for preference lists. For some cases of preference types and thresholds, we give O(n) algorithms whose running time is independent of w.

关键词： Seating arrangement linear algorithm FPT algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear algorithm of Spatial Straightness for Five Points

A Linear Algorithm of Spatial Straightness for Five Points

引用

2nd International Conference on Mechatronics and Intelligent Materials (MIM 2012)

作者： Meng, Fanwu Xu, Chunguang Hao, Juan Beijing Inst Technol Sch Mech Engn Beijing 100081 Peoples R China

ISBN: (纸本)9783037853849

It is a non-linear problem to evaluate the minimum zone spatial (3-D) straightness. Because of the disadvantages of evaluating spatial straightness error with traditional method, such as difficulty in solving the non-linear equation, the evaluating precision is lower. This paper develops a solution that can transform the non-linear problem into a linear problem. The solution can obtain more exact results than traditional method using results of LSC as initial conditions. This methodology can also be applied to the problems of computing the minimum circumscribed cylinder and the maximum inscribed cylinder. The effectiveness and efficiency of the novel approach are illustrated by two examples.

关键词： spatial straightness minimum circumscribed cylinder linear algorithm

来源：评论

学校读者我要写书评

暂无评论

An evaluation of cloud-based mobile services with limited capacity: a linear approach

引用

SOFT COMPUTING 2017年第16期21卷 4523-4530页

作者： Skourletopoulos, Georgios Mavromoustakis, Constandinos X. Mastorakis, George Batalla, Jordi Mongay Sahalos, John N. Univ Nicosia Dept Comp Sci Nicosia Cyprus Technol Educ Inst Crete Dept Informat Engn Iraklion Crete Greece Warsaw Univ Technol Nowowiejska Str 15-19 PL-00665 Warsaw Poland Univ Nicosia Dept Elect & Comp Engn Nicosia Cyprus

Mobile computing is pervading networks at an increasing speed as mobile devices are used with diverse forms of wireless technologies to access data. This paper evaluates different cloud-supported mobile services subject to limited capacity, as the selection of a service may introduce additional costs, such as those that derive from the additional amount of memory required for processing. In this context, a novel linear model and algorithm in the mobile cloud computing environment are proposed from the service capacity perspective, considering the cost that derives from the unused capacity. The probability of overutilization or underutilization of the selected service is also researched, once a linear growth in the number of users occurs. To further make effective and strategic investment decisions when selecting the appropriate cloud-based mobile service to lease off, the model formulation is based on a cost-benefit appraisal. The proposed quantification approach is evaluated with respect to four different case scenarios, exploiting a web tool that has been developed as a proof of concept and implementing the algorithm to calculate and compare the benefits and costs in the mobile cloud-based service level.

关键词： linear model linear algorithm Limited capacity Lease web services Mobile cloud computing Mobile cloud-based service level Overutilization IT investment Decision making methodology

来源：评论

学校读者我要写书评

暂无评论

An algorithm of Pose Estimation Based on Conic Correspondences

An Algorithm of Pose Estimation Based on Conic Correspondenc...

引用

IEEE International Conference on Robotics and Biomimetics (ROBIO)

作者： Wang, Wenchao Zhang, Xu Qi, Yong Cheng, Wei Shanghai Univ Sch Mechatron Engn & Automat Shanghai Peoples R China

ISBN: (纸本)9781538637425

As we all know, in computer vision, conics are widely applied as one of the most underlying image features together with points or lines and sometimes the correspondences of the points or lines are not available, so under the circumstances, conics are also a good choice which could be identified robustly. This paper gives a linear algorithm of estimating pose of camera based on the correspondences of conic from world plane to image plane system. The numbers of pairs of conics needed are equal or greater to three. The core of the algorithm is the solution of homography. In this case, we give an overdetermined set of linear equations and the solution got by the singular value decomposition is the homography. Hence, the proposed formulation leads to an algorithm that is efficient and easy to implement. On the basis of homography is known, the pose of camera can be estimated with matrix operations. In addition, the validity and robustness of the algorithm is verified though experiments with simulation data and real measured data. The main novel points in this paper are: First, comparing with the traditional methods, we use conics with the advantages more common, easier to be extracted and more stable than points;Second, using matrix transformation and singular value decomposition only, avoids solving polynomials so that the complexity of the algorithm is reduced greatly.

关键词： linear algorithm pose estimation of camera conics homography

来源：评论

学校读者我要写书评

暂无评论

Domain adaptation of image classification based on collective target nearest-neighbor representation

引用

JOURNAL OF ELECTRONIC IMAGING 2016年第3期25卷 033006-033006页

作者： Tang, Song Ye, Mao Liu, Qihe Li, Fan Univ Elect Sci & Technol China Sch Comp Sci & Engn Ctr Robot Key Lab NeuroinformatMinist Educ Chengdu 611731 Peoples R China

In many practical applications, we frequently face the awkward problem in which an image classifier trained in a scenario is difficult to use in a new scenario. Traditionally, the probability inference-based methods are used to solve this problem. From the point of image representation, we propose an approach for domain adaption of image classification. First, all source samples are supposed to form the dictionary. Then, we encode the target sample by combining this dictionary and the local geometric information. Based on this new representation, called target nearest-neighbor representation, image classification can obtain good performance in the target domain. Our core contribution is that the nearest-neighbor information of the target sample is technically exploited to form more robust representation. Experimental results confirm the effectiveness of our method. (C) 2016 SPIE and IS&T

关键词： domain adaptation object classification linear algorithm nearest-neighbor information

来源：评论

学校读者我要写书评

暂无评论

Static and dynamic source locations in undirected networks

引用

TOP 2015年第3期23卷 619-646页

作者： Turner, Lara Gross, Dwi Poetranto Hamacher, Horst W. Krumke, Sven O. Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany INFORM GmbH D-52076 Aachen Germany

Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented;for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.

关键词： Source location problem Single cover problem Matroid (Dual) greedy algorithm (Minimal) deficient set Plural cover problem Tree network linear algorithm Pseudo-polynomial algorithm Fully polynomial-time approximation scheme Dynamic flow NP-hardness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：