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

Polynomial-time metrics for attributed trees

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2005年第7期27卷 1087-1099页

作者： Torsello, A Hidovic-Rowe, D Pelillo, M Univ Ca Foscari di Venezia Dipartimento Informat I-30172 Venice Italy Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

We address the problem of comparing attributed trees and propose four novel distance measures centered around the notion of a maximal similarity common subtree. The proposed measures are general and defined on trees endowed with either symbolic or continuous- valued attributes and can be applied to rooted as well as unrooted trees. We prove that our measures satisfy the metric constraints and provide a polynomial- time algorithm to compute them. This is a remarkable and attractive property, since the computation of traditional edit- distance- based metrics is, in general, NP- complete, at least in the unordered case. We experimentally validate the usefulness of our metrics on shape matching tasks and compare them with ( an approximation of) edit- distance.

关键词： metrics tree matching polynomial time algorithms shape recognition

来源：评论

学校读者我要写书评

暂无评论

Predictability for Finite State Machines: a set-membership approach

引用

IFAC-PapersOnLine 2018年第7期51卷 355-360页

作者： Fiore, Gabriella Santis, Elena De Di Benedetto, Maria Domenica Center of Excellence DEWS LAquila67100 Italy

In this paper we investigate how to predict the future occurrence of specific discrete states of a finite state system on the basis of the observations. Predictability property is defined with respect to a subset of discrete states, called critical set, representing for example faulty states or, more generally, any subset of states which is of particular interest from the system's behavior point of view. We define and characterize eventual and critical predictability properties by means of a set-membership-based formalism. Using the proposed framework, it is possible to check predictability properties with polynomial time algorithms. © 2018

关键词： Discrete event simulation Finite automata Observability Polynomial approximation Diagnosability Discrete state Finite state systems Polynomial time algorithms predictability Set membership Set membership approach

来源：评论

学校读者我要写书评

暂无评论

Two-Station Single Track Scheduling Problem

引用

IFAC-PapersOnLine 2016年第12期49卷 231-236页

作者： Zinder, Yakov Lazarev, Alexander A. Musatova, Elena G. Tarasov, Ilia A. Khusnullin, Nail F. University of Technology Sydney Australia International Laboratory of Decision Choice and Analysis National Research University Higher School of Economics Lomonosov Moscow State University Institute of Physics and Technology State University Institute of control sciences Moscow United States Institute of control sciences Moscow United States Lomonosov Moscow State University Institute of control sciences Moscow United States

Single track segments are common in various railway networks, in particular in various supply chains. For such a segment, connecting two stations, the trains form two groups, depending on what station is the initial station for the journey between these two stations. Within a group the trains differ by their cost functions. It is assumed that the single track is sufficiently long so several trains can travel in the same direction simultaneously. The paper presents polynomial-time algorithms for different versions of this two-station train scheduling problem with a single railway track. The considered models differ from each other by their objective functions. © 2016

关键词： Scheduling Cost functions Operations research Polynomial approximation Railroads Supply chains Objective functions Polynomial time algorithms Railway network Railway track Scheduling problem Single tracks Train scheduling

来源：评论

学校读者我要写书评

暂无评论

Heuristic algorithms for two-machine job shop problem under availability constraints on one machine: makespan minimization

引用

IFAC-PapersOnLine 2018年第11期51卷 1065-1070页

作者： Benttaleb, Mourad Hnaien, Faicel Yalaoui, Farouk ICD-LOSI Université de Technologie de Troyes UMR CNRS 6281 12 Rue Marie Curie Troyes Cedex42060-10004 CS France

We discuss the two-machine job shop scheduling problem with availability constraints on one machine for maximum completion time (makespan) minimization. We consider the problem when unavailability periods are planned in advance and operations are non-preemptive. Firstly, some propositions considering Jackson's rule under availability constraints are introduced. Then, we provide polynomial-time algorithm based on Jackson's rule and an iterated local search tabu based algorithm exploiting the optimality of Jackson's rule between each two consecutive availability periods to solve the problem. Finally, we present some experimental results. © 2018

关键词： Job shop scheduling Approximation algorithms Heuristic algorithms Local search (optimization) Machine shops Polynomial approximation Problem solving Availability constraints Iterated local search Job shop Job shop scheduling problems Makespan Maximum completion time Polynomial time algorithms Unavailability periods

来源：评论

学校读者我要写书评

暂无评论

Inventory replenishment planning with a full truckload cost and a full return policy

引用

IFAC-PapersOnLine 2018年第11期51卷 259-263页

作者： Farhat, Mlouka Akbalik, Ayse Sauer, Nathalie Hadj-Alouane, Atidel B. Université de Lorraine LGIPM Technopôle METZ57073 France Université de Lorraine LCOMS Technopôle METZ57073 France Université de Tunis El Manar OASIS École Nationale d'Ingénieurs de Tunis BP 37 Le Belvédère Tunis1002 Tunisia

This paper addresses the single-item uncapacitated lot sizing problem with batch ordering under the buyback contract between a retailer and a supplier. The form of this type of contract consists in returning all the unused products at the end of every w periods (with w ≥ 1) to the supplier. This problem is studied with only full batches (OFB), which means that the procurement in each period is restricted to a multiple of a constant batch size, where each demand is satisfied without backlogging and all cost parameters are time-dependent. In this extension, we consider a stepwise discontinuous procurement cost structure due to the fixed cost per batch replenished, incurred by the retailer, in addition to the classical lot sizing costs. Several properties of the optimal solution are proposed to develop an efficient dynamic programming algorithm performed in time complexity O(Tw). © 2018

关键词： Costs Dynamic programming Polynomial approximation Buy back contracts Dynamic programming algorithm Inventory replenishment Lot sizing Lot sizing problems Optimal solutions Polynomial time algorithms Procurement costs

来源：评论

学校读者我要写书评

暂无评论

Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem

引用

IFAC-PapersOnLine 2016年第12期49卷 651-655页

作者： Chentsov, Alexander Khachay, Michael Khachay, Daniel Krasovsky Institute of Mathematics and Mechanics Ural Federal University 16 S.Kovalevskoy str. 19 Mira str Ekaterinburg620990 Russia

We consider the combinatorial optimization problem of visiting clusters of a fixed number of nodes (cities), where, on the set of clusters should be visited according to some kind of partial order defined by additional precedence constraints. This problem is a kind of the Asymmetric Generalized Traveling Salesman Problem (AGTSP). To find an optimal solution of the problem, we propose a dynamic programming based on algorithm extending the well known Held and Karp technique. In terms of special type of precedence constraints, we describe subclasses of the problem, with polynomial (or even linear) in n upper bounds of time complexity. © 2016

关键词： Traveling salesman problem Clustering algorithms Combinatorial optimization Computational complexity Dynamic programming Combinatorial optimization problems Fixed numbers Generalized traveling salesman problem Linear time algorithms Optimal solutions Partial order Precedence constraints time complexity

来源：评论

学校读者我要写书评

暂无评论

Research on the fine DEM of the open-pit establishment method considering the steps character

引用

Procedia Earth and Planetary Science 2009年第1期1卷 1128-1132页

作者： Xin, Sui Wei-dong, Song Ai-gong, Xu Lan-yong, Li Liaoning Technical University No.47 Zhonghua Road Fuxin 123000 China

At present, triangulated irregular net is the best method for landform expression, so we discusses the method of applying triangulated irregular net to establish the DEM of open-pit in this paper. Because of the complicated landform characteristic of open-pit, corresponding constraint condition should be considered in the process of building model, otherwise it will appear a phenomenon that the flight of the step is cut. The method of triangulated irregular net establishment includes three kinds of algorithm, that is, divide and conquer algorithm, piecemeal intervene in algorithm and triangle net growth algorithm. Each algorithm has its own advantage and disadvantage, Combined with the actual situation of the mining area, this paper adopts the constrained triangulated irregular net of one-time algorithm, through spatial data extraction, topological relations generation and spatial indexing generation, then finally builds up constrained triangulated irregular net within boundary line. © 2009.

关键词： algorithms Landforms Boundary lines Building model Constraint conditions Divide and conquer algorithm Growth algorithms Mining areas Open pit Spatial data Spatial indexing Spatial indices time algorithms Topological relations Triangulated irregular net

来源：评论

学校读者我要写书评

暂无评论

Fast, Sound, and effectively complete dynamic race prediction

Fast, Sound, and effectively complete dynamic race predictio...

引用

Proceedings of the ACM on Programming Languages

作者： Pavlogiannis, Andreas Aarhus University Aabogade 34 Aarhus8200 Denmark

Writing concurrent programs is highly error-prone due to the nondeterminism in interprocess communication. The most reliable indicators of errors in concurrency are data races, which are accesses to a shared resource that can be executed concurrently. We study the problem of predicting data races in lock-based concurrent programs. The input consists of a concurrent trace t , and the task is to determine all pairs of events of t that constitute a data race. The problem lies at the heart of concurrent verification and has been extensively studied for over three decades. However, existing polynomial-time sound techniques are highly incomplete and can miss simple races. In this work we develop M2: a new polynomial-time algorithm for this problem, which has no false positives. In addition, our algorithm is complete for input traces that consist of two processes, i.e., it provably detects all races in the trace. We also develop sufficient criteria for detecting completeness dynamically in cases of more than two *** make an experimental evaluation of our algorithm on a challenging set of benchmarks taken from recent literature on the topic. Our algorithm soundly reports hundreds of real races, many of which are missed by existing methods. In addition, using our dynamic completeness criteria, M2 concludes that it has detected all races in the benchmark set, hence the reports are both sound and complete. Finally, its running times are comparable, and often smaller than the theoretically fastest, yet highly incomplete, existing methods. To our knowledge, M2 is the first sound algorithm that achieves such a level of performance on both running time and completeness of the reported races. © 2020 Copyright held by the owner/author(s).

关键词： Polynomial approximation Predictive analytics Concurrency Concurrent program Experimental evaluation Interprocess communication Polynomial time algorithms Race detection Sound and complete Writing concurrent programs

来源：评论

学校读者我要写书评

暂无评论

Learning graphs from noisy epidemic cascades 7

Learning graphs from noisy epidemic cascades

引用

Proceedings of the ACM on Measurement and Analysis of Computing Systems

作者： Hoffmann, Jessica Caramanis, Constantine University of Texas at Austin AustinTX78712 United States

ISBN: (纸本)9781450366786

We consider the problem of learning the weighted edges of a graph by observing the noisy times of infection for multiple epidemic cascades on this graph. Past work has considered this problem when the cascade information, i.e., infection times, are known exactly. Though the noisy setting is well motivated by many epidemic processes (e.g., most human epidemics), to the best of our knowledge, very little is known about when it is solvable. Previous work on the no-noise setting critically uses the ordering information. If noise can reverse this – a node’s reported (noisy) infection time comes after the reported infection time of some node it infected – then we are unable to see how previous results can be extended. We therefore tackle two versions of the noisy setting: the limited-noise setting, where we know noisy times of infections, and the extreme-noise setting, in which we only know whether or not a node was infected. We provide a polynomial time algorithm for recovering the structure of bidirectional trees in the extreme-noise setting, and show our algorithm matches lower bounds established in the no-noise setting, and hence is optimal. We extend our results for general degree-bounded graphs, where again we show that our (poly-time) algorithm can recover the structure of the graph with optimal sample complexity. We also provide the first efficient algorithm to learn the weights of the bidirectional tree in the limited-noise setting. Finally, we give a polynomial time algorithm for learning the weights of general bounded-degree graphs in the limited-noise setting. This algorithm extends to general graphs (at the price of exponential running time), proving the problem is solvable in the general case. All our algorithms work for any noise distribution, without any restriction on the variance. © 2019 Association for Computing Machinery.

关键词： Trees (mathematics) Epidemiology Forestry Graph algorithms Graphic methods Inverse problems Learning algorithms Polynomial approximation Bounded degree graphs Contact process Epidemic cascades Epidemics Exponential running time Noise distribution Polynomial time algorithms SIR model

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-394

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-394 by published by

关键词： bounded condition composition constant bounded domatic number graph graph decision graphs linear linear time local condition mit-lcs-tr-394 polynomial polynomial time positive integer spanning spanning tree subgraph theorem time algorithms treewidth vertex

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：