Border basis detection is NP-complete

Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Grobner bases termed as Grobner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.

NP难问题的算法和实验性研究

NP难是计算机科学中的一个重要概念和核心问题，自从它的提出到现在， 人们已经得到了很多重要的理论结果。直观上讲，一个问题一旦被证明是NP难 的就意味着我们很难找到该问题的一个多项式时间的有效算法。但从实用的角 度讲，对于应用中遇到的问题，单单是证明它很难（是NP难的）是不够的，如何 在合理的时间内求解实际问题也是必须解决的现实问题。本文主要侧重于NP难 问题的算法和实验性研究，研究对象主要是可满足性问题、图的顶点染色、图 的子图匹配等NP难问题，以及可满足性模理论的解空间计算和体积估算等扩展 问题。 围绕几个著名的问题，本文的主要工作如下： 针对图染色问题，日本研究人员提出了一种通过组合小图单元得到大的难 实例的方法。他们通过试错的方式手工找到了7个小图单元。我们提出了一种新 的构造算法来系统地生成这类小图单元，用我们的算法生成的难图染色实例， 主流的图染色工具需要指数时间才能求解；在一些专门求解色数比较小的图的 图染色工具上我们的算法生成的实例更难求解。针对皇后图染色问题，我们利 用模型查找工具SEM来对这类问题进行求解，在求解过程中提出了新的变量选 择策略，发现比简单地使用可满足性问题工具和图染色工具效果要好。 针对语义Web推理中的关键问题RDF蕴含关系的判定问题，我们利用从子 图同构问题到可满足性问题的编码方案，把它转化为命题逻辑公式的可满足性 判定问题，并采用了启发式的方法对编码过程进行必要的化简得到较少的布尔 公式，然后再利用高效的可满足性问题工具来求解。这种转化为可满足性问题 的方法，是跟RDF简单蕴含的模型论语义结合比较自然的一个方法。在小规模 实例上，这种方法的效果也很好。 针对布尔和数值混合约束的公式，即可满足性模理论（线性理论）公式的 体积计算这一新问题，我们首先给出一个直接计算体积的方法，然后提出一个 改进的算法，并研究了如何通过引入可满足性模理论中的技术来尝试对该算法 进一步地改进。我们实现了工具并做了实验。在一个实际的程序实例上，我们 还就“热门路径”问题做了实例研究和探讨。 体积计算是一个有广泛应用背景的经典难题（#P难的），但以前的方法要 么只能处理线性约束，要么只具有理论价值（不够实用）；针对含非线性约束的 体积计算问题我们提出了实用的算法，并设计了相应的工具，在低维实例有很 好的逼近效果。

Hard tissue formation adjacent to implants of various size and configuration immediately placed into extraction sockets: an experimental study in dogs

Objectives To evaluate the influence of implant size and configuration on osseointegration in implants immediately placed into extraction sockets. Material and methods Implants were installed immediately into extraction sockets in the mandibles of six Labrador dogs. In the control sites, cylindrical transmucosal implants (3.3 mm diameter) were installed, while in the test sites, larger and conical (root formed, 5 mm diameter) implants were installed. After 4 months of healing, the resorptive patterns of the alveolar crest were evaluated histomorphometrically. Results With one exception, all implants were integrated in mineralized bone, mainly composed of mature lamellar bone. The alveolar crest underwent resorption at the control as well as at the test implants. This resorption was more pronounced at the buccal aspects and significantly greater at the test (2.7 +/- 0.4 mm) than at the control implants (1.5 +/- 0.6 mm). However, the control implants were associated with residual defects that were deeper at the lingual than at the buccal aspects, while these defects were virtually absent at test implants. Conclusions The installment of root formed wide implants immediately into extraction sockets will not prevent the resorption of the alveolar crest. In contrast, this resorption is more marked both at the buccal and lingual aspects of root formed wide than at standard cylindrical implants. To cite this article:Caneva M, Salata LA, de Souza SS, Bressan E, Botticelli D, Lang NP. Hard tissue formation adjacent to implants of various size and configuration immediately placed into extraction sockets: an experimental study in dogs.Clin. Oral Impl. Res. 21, 2010; 885-895.doi: 10.1111/j.1600-0501.2010.01931.x.

Hard tissue formation adjacent to implants of various size and configuration immediately placed into extraction sockets: an experimental study in dogs

ObjectivesTo evaluate the influence of implant size and configuration on osseointegration in implants immediately placed into extraction sockets.Material and methodsImplants were installed immediately into extraction sockets in the mandibles of six Labrador dogs. In the control sites, cylindrical transmucosal implants (3.3 mm diameter) were installed, while in the test sites, larger and conical (root formed, 5 mm diameter) implants were installed. After 4 months of healing, the resorptive patterns of the alveolar crest were evaluated histomorphometrically.ResultsWith one exception, all implants were integrated in mineralized bone, mainly composed of mature lamellar bone. The alveolar crest underwent resorption at the control as well as at the test implants. This resorption was more pronounced at the buccal aspects and significantly greater at the test (2.7 +/- 0.4 mm) than at the control implants (1.5 +/- 0.6 mm). However, the control implants were associated with residual defects that were deeper at the lingual than at the buccal aspects, while these defects were virtually absent at test implants.ConclusionsThe installment of root formed wide implants immediately into extraction sockets will not prevent the resorption of the alveolar crest. In contrast, this resorption is more marked both at the buccal and lingual aspects of root formed wide than at standard cylindrical implants.To cite this article:Caneva M, Salata LA, de Souza SS, Bressan E, Botticelli D, Lang NP. Hard tissue formation adjacent to implants of various size and configuration immediately placed into extraction sockets: an experimental study in dogs.Clin. Oral Impl. Res. 21, 2010; 885-895.doi: 10.1111/j.1600-0501.2010.01931.x.

Replication-based inference algorithms for hard computational problems

Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation. © 2013 American Physical Society.

Optimization of container process at seaport terminals

Seaport container terminals are an important part of the logistics systems in international trades. This paper investigates the relationship between quay cranes, yard machines and container storage locations in a multi-berth and multi-ship environment. The aims are to develop a model for improving the operation efficiency of the seaports and to develop an analytical tool for yard operation planning. Due to the fact that the container transfer times are sequence-dependent and with the large number of variables involve, the proposed model cannot be solved in a reasonable time interval for realistically sized problems. For this reason, List Scheduling and Tabu Search algorithms have been developed to solve this formidable and NP-hard scheduling problem. Numerical implementations have been analysed and promising results have been achieved.

Scheduling a flow-shop with combined buffer conditions

In this paper, No-Wait, No-Buffer, Limited-Buffer, and Infinite-Buffer conditions for the flow-shop problem (FSP) have been investigated. These four different buffer conditions have been combined to generate a new class of scheduling problem, which is significant for modelling many real-world scheduling problems. A new heuristic algorithm is developed to solve this strongly NP-hard problem. Detailed numerical implementations have been analysed and promising results have been achieved.

Genetic algorithms to schedule container transfers at multimodal terminals

Optimising the container transfer schedule at the multimodal terminals is known to be NP-hard, which implies that the best solution becomes computationally infeasible as problem sizes increase. Genetic Algorithm (GA) techniques are used to reduce container handling/transfer times and ships' time at the port by speeding up handling operations. The GA is chosen due to the relatively good results that have been reported even with the simplest GA implementations to obtain near-optimal solutions in reasonable time. Also discussed, is the application of the model to assess the consequences of increased scheduled throughput time as well as different strategies such as the alternative plant layouts, storage policies and number of yard machines. A real data set used for the solution and subsequent sensitivity analysis is applied to the alternative plant layouts, storage policies and number of yard machines.

Scheduling techniques to optimise rail operations

In Australia, railway systems play a vital role in transporting the sugarcane crop from farms to mills. The sugarcane transport system is very complex and uses daily schedules, consisting of a set of locomotives runs, to satisfy the requirements of the mill and harvesters. The total cost of sugarcane transport operations is very high; over 35% of the total cost of sugarcane production in Australia is incurred in cane transport. Efficient schedules for sugarcane transport can reduce the cost and limit the negative effects that this system can have on the raw sugar production system. There are several benefits to formulating the train scheduling problem as a blocking parallel-machine job shop scheduling (BPMJSS) problem, namely to prevent two trains passing in one section at the same time; to keep the train activities (operations) in sequence during each run (trip) by applying precedence constraints; to pass the trains on one section in the correct order (priorities of passing trains) by applying disjunctive constraints; and, to ease passing trains by solving rail conflicts by applying blocking constraints and Parallel Machine Scheduling. Therefore, the sugarcane rail operations are formulated as BPMJSS problem. A mixed integer programming and constraint programming approaches are used to describe the BPMJSS problem. The model is solved by the integration of constraint programming, mixed integer programming and search techniques. The optimality performance is tested by Optimization Programming Language (OPL) and CPLEX software on small and large size instances based on specific criteria. A real life problem is used to verify and validate the approach. Constructive heuristics and new metaheuristics including simulated annealing and tabu search are proposed to solve this complex and NP-hard scheduling problem and produce a more efficient scheduling system. Innovative hybrid and hyper metaheuristic techniques are developed and coded using C# language to improve the solutions quality and CPU time. Hybrid techniques depend on integrating heuristic and metaheuristic techniques consecutively, while hyper techniques are the complete integration between different metaheuristic techniques, heuristic techniques, or both.

A simulated annealing algorithm for energy efficient virtual machine placement

Improving energy efficiency has become increasingly important in data centers in recent years to reduce the rapidly growing tremendous amounts of electricity consumption. The power dissipation of the physical servers is the root cause of power usage of other systems, such as cooling systems. Many efforts have been made to make data centers more energy efficient. One of them is to minimize the total power consumption of these servers in a data center through virtual machine consolidation, which is implemented by virtual machine placement. The placement problem is often modeled as a bin packing problem. Due to the NP-hard nature of the problem, heuristic solutions such as First Fit and Best Fit algorithms have been often used and have generally good results. However, their performance leaves room for further improvement. In this paper we propose a Simulated Annealing based algorithm, which aims at further improvement from any feasible placement. This is the first published attempt of using SA to solve the VM placement problem to optimize the power consumption. Experimental results show that this SA algorithm can generate better results, saving up to 25 percentage more energy than First Fit Decreasing in an acceptable time frame.

Optimally increasing secure connectivity in multihop wireless ad hoc networks

We consider the problem of how to maximize secure connectivity of multi-hop wireless ad hoc networks after deployment. Two approaches, based on graph augmentation problems with nonlinear edge costs, are formulated. The first one is based on establishing a secret key using only the links that are already secured by secret keys. This problem is in NP-hard and does not accept polynomial time approximation scheme PTAS since minimum cutsets to be augmented do not admit constant costs. The second one is based of increasing the power level between a pair of nodes that has a secret key to enable them physically connect. This problem can be formulated as the optimal key establishment problem with interference constraints with bi-objectives: (i) maximizing the concurrent key establishment flow, (ii) minimizing the cost. We show that both problems are NP-hard and MAX-SNP (i.e., it is NP-hard to approximate them within a factor of 1 + e for e > 0 ) with a reduction to MAX3SAT problem. Thus, we design and implement a fully distributed algorithm for authenticated key establishment in wireless sensor networks where each sensor knows only its one- hop neighborhood. Our witness based approaches find witnesses in multi-hop neighborhood to authenticate the key establishment between two sensor nodes which do not share a key and which are not connected through a secure path.

Design and analysis of key management schemes for distributed wireless sensor networks

Secure communications in distributed Wireless Sensor Networks (WSN) operating under adversarial conditions necessitate efficient key management schemes. In the absence of a priori knowledge of post-deployment network configuration and due to limited resources at sensor nodes, key management schemes cannot be based on post-deployment computations. Instead, a list of keys, called a key-chain, is distributed to each sensor node before the deployment. For secure communication, either two nodes should have a key in common in their key-chains, or they should establish a key through a secure-path on which every link is secured with a key. We first provide a comparative survey of well known key management solutions for WSN. Probabilistic, deterministic and hybrid key management solutions are presented, and they are compared based on their security properties and re-source usage. We provide a taxonomy of solutions, and identify trade-offs in them to conclude that there is no one size-fits-all solution. Second, we design and analyze deterministic and hybrid techniques to distribute pair-wise keys to sensor nodes before the deployment. We present novel deterministic and hybrid approaches based on combinatorial design theory and graph theory for deciding how many and which keys to assign to each key-chain before the sensor network deployment. Performance and security of the proposed schemes are studied both analytically and computationally. Third, we address the key establishment problem in WSN which requires key agreement algorithms without authentication are executed over a secure-path. The length of the secure-path impacts the power consumption and the initialization delay for a WSN before it becomes operational. We formulate the key establishment problem as a constrained bi-objective optimization problem, break it into two sub-problems, and show that they are both NP-Hard and MAX-SNP-Hard. Having established inapproximability results, we focus on addressing the authentication problem that prevents key agreement algorithms to be used directly over a wireless link. We present a fully distributed algorithm where each pair of nodes can establish a key with authentication by using their neighbors as the witnesses.

Complexity of increasing the secure connectivity in wireless ad hoc networks

We consider the problem of maximizing the secure connectivity in wireless ad hoc networks, and analyze complexity of the post-deployment key establishment process constrained by physical layer properties such as connectivity, energy consumption and interference. Two approaches, based on graph augmentation problems with nonlinear edge costs, are formulated. The first one is based on establishing a secret key using only the links that are already secured by shared keys. This problem is in NP-hard and does not accept polynomial time approximation scheme PTAS since minimum cutsets to be augmented do not admit constant costs. The second one extends the first problem by increasing the power level between a pair of nodes that has a secret key to enable them physically connect. This problem can be formulated as the optimal key establishment problem with interference constraints with bi-objectives: (i) maximizing the concurrent key establishment flow, (ii) minimizing the cost. We prove that both problems are NP-hard and MAX-SNP with a reduction to MAX3SAT problem.

A novel method for finding similarities between unordered trees using matrix data model

Trees are capable of portraying the semi-structured data which is common in web domain. Finding similarities between trees is mandatory for several applications that deal with semi-structured data. Existing similarity methods examine a pair of trees by comparing through nodes and paths of two trees, and find the similarity between them. However, these methods provide unfavorable results for unordered tree data and result in yielding NP-hard or MAX-SNP hard complexity. In this paper, we present a novel method that encodes a tree with an optimal traversing approach first, and then, utilizes it to model the tree with its equivalent matrix representation for finding similarity between unordered trees efficiently. Empirical analysis shows that the proposed method is able to achieve high accuracy even on the large data sets.

A hybrid constructive heuristic and simulated annealing for railway crew scheduling

Railway crew scheduling problem is the process of allocating train services to the crew duties based on the published train timetable while satisfying operational and contractual requirements. The problem is restricted by many constraints and it belongs to the class of NP-hard. In this paper, we develop a mathematical model for railway crew scheduling with the aim of minimising the number of crew duties by reducing idle transition times. Duties are generated by arranging scheduled trips over a set of duties and sequentially ordering the set of trips within each of duties. The optimisation model includes the time period of relief opportunities within which a train crew can be relieved at any relief point. Existing models and algorithms usually only consider relieving a crew at the beginning of the interval of relief opportunities which may be impractical. This model involves a large number of decision variables and constraints, and therefore a hybrid constructive heuristic with the simulated annealing search algorithm is applied to yield an optimal or near-optimal schedule. The performance of the proposed algorithms is evaluated by applying computational experiments on randomly generated test instances. The results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time for large-sized problems.