Job-shop scheduling in a body shop

We study a generalized job-shop problem called the body shop scheduling problem (BSSP). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. BSSP corresponds to a job-shop problem where the operations of a job have to follow alternating routes on the machines, certain operations of different jobs are not allowed to be processed at the same time and after processing an operation of a certain job a machine might be unavailable for a given time for operations of other jobs. As main results we will show that for three jobs and four machines the special case where only one machine is used by more than one job is already $\mathcal NP $ -hard. This also implies that the single machine scheduling problem that asks for a makespan minimal schedule of three chains of operations with delays between the operations of a chain is $\mathcal NP $ -hard. On the positive side, we present a polynomial algorithm for the two job case and a pseudo-polynomial algorithm together with an FPTAS  for an arbitrary but constant number of jobs. Hence for a constant number of jobs we fully settle the complexity status of the problem.     

Query containment under bag and bag-set semantics

Conjunctive queries (CQs) are at the core of query languages encountered in many logic-based research fields such as AI, or database systems. The majority of existing work assumes set semantics but often in real applications the manipulation of duplicate tuples is required. One of the major problems that arises as part of advanced features of query optimization, data integration, query reformulation and many other research topics is testing for containment of such queries. In this work, we investigate the complexity of query containment problem for CQs under bag semantics (i.e. duplicate tuples are allowed in both the database and the results of queries) and under bag-set semantics (i.e. duplicates are allowed in the result of the queries but not in the database). We derive complexity results for these problems for five major subclasses of CQs; and we also find necessary conditions for CQ query containment. The general case of these problems remains open.     

Optimal complexity reduction of polyhedral piecewise affine systems

This paper focuses on the NP-hard problem of reducing the complexity of piecewise polyhedral systems (e.g. polyhedral piecewise affine (PWA) systems). The results are fourfold. Firstly, the paper presents two computationally attractive algorithms for optimal complexity reduction that, under the assumption that the system is defined over the cells of a hyperplane arrangement, derive an equivalent polyhedral piecewise system that is minimal in the number of polyhedra. The algorithms are based on the cells and the markings of the hyperplane arrangement. In particular, the first algorithm yields a set of disjoint (non overlapping) merged polyhedra by executing a branch and bound search on the markings of the cells. The second approach leads to non-disjoint (overlapping) polyhedra by formulating and solving an equivalent (and well-studied) logic minimization problem. Secondly, the results are extended to systems defined on general polyhedral partitions (and not on cells of hyperplane arrangements). Thirdly, the paper proposes a technique to further reduce the complexity of piecewise polyhedral systems if the introduction of an adjustable degree of error is acceptable. Fourthly, the paper shows that based on the notion of the hyperplane arrangement PWA state feedback control laws can be implemented efficiently. Three examples, including a challenging industrial problem, illustrate the algorithms and show their computational effectiveness in reducing the complexity by up to one order of magnitude.     

Advanced parallel strategy for strongly coupled fast transient fluid-structure dynamics with dual management of kinematic constraints

Simulating fast transient phenomena involving fluids and structures in interaction for safety purposes requires both accurate and robust algorithms, and parallel computing to reduce the calculation time for industrial models. Managing kinematic constraints linking fluid and structural entities is thus a key issue and this contribution promotes a dual approach over the classical penalty approach, introducing arbitrary coefficients in the solution. This choice however severely increases the complexity of the problem, mainly due to non-permanent kinematic constraints. An innovative parallel strategy is therefore described, whose performances are demonstrated on significant examples exhibiting the full complexity of the target industrial simulations.     

Easy intruder deduction problems with homomorphisms

We present complexity results for the verification of security protocols. Since the perfect cryptography assumption is unrealistic for cryptographic primitives with visible algebraic properties, we extend the classical Dolev-Yao model by permitting the intruder to exploit these properties. More precisely, we are interested in theories such as Exclusive or and Abelian groups in combination with the homomorphism axiom. We show that the intruder deduction problem is in PTIME in both cases, improving the EXPTIME complexity results of Lafourcade, Lugiez and Treinen.     

Learning expressions and programs over monoids

We study the problem of learning an unknown function represented as an expression or a program over a known finite monoid. As in other areas of computational complexity where programs over algebras have been used, the goal is to relate the computational complexity of the learning problem with the algebraic complexity of the finite monoid. Indeed, our results indicate a close connection between both kinds of complexity. We focus on monoids which are either groups or aperiodic, and on the learning model of exact learning from queries. For a group G, we prove that expressions over G are efficiently learnable if G is nilpotent, and impossible to learn efficiently (under cryptographic assumptions) if G is nonsolvable. We present some results for restricted classes of solvable groups, and point out a connection between their efficient learnability and the existence of lower bounds on their computational power in the program model. For aperiodic monoids, our results seem to indicate that the monoid class known as DA captures exactly learnability of expressions by polynomially many Evaluation queries. When using programs instead of expressions, we show that our results for groups remain true, while the situation is quite different for aperiodic monoids.     

基于Windows 2003远程终端PUP共享服务平台的组建和应用

我局新建成的新一代天气雷达产品共享服务平台(PUP 共享服务平台),在基于 Windows 2003 Server 提供的远程终端服务功能的基础上,实现了多个客户端同时使用服务器的气象资源的功能。本文从远程终端服务的服务器端、客户端、PUP 软件安装等方面的技术实现角度,以及通过它方便地扩展为气象信息共享平台等方面,主要介绍了 PUP 共享服务平台的组建和应用情况。     

An information statistics approach to data stream and communication complexity

We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving conditional information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.Our paradigm leads to two main results:(1) An improved lower bound for the multi-party set-disjointness problem in the general communication complexity model, and a nearly optimal lower bound in the one-way communication model. As a consequence, we show that for any real k>2, approximating the kth frequency moment in the data stream model requires essentially Ω(n1−2/k) space; this resolves a conjecture of Alon et al. (J. Comput. System Sci. 58(1) (1999) 137).(2) A lower bound for the L_p approximation problem in the general communication model; this solves an open problem of Saks and Sun (in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 360-369). As a consequence, we show that for p>2, approximating the L_p norm to within a factor of n^ε in the data stream model with constant number of passes requires Ω(n1−4ε−2/p) space.     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

A faster off-line algorithm for the TCP acknowledgement problem

In a recent paper [Proceedings of STOC'98, 1998, pp. 389-398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n²) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures.In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).     

A parametric analysis of the state-explosion problem in model checking

In model checking, the state-explosion problem occurs when one checks a nonflat system, i.e., a system implicitly described as a synchronized product of elementary subsystems. In this paper, we investigate the complexity of a wide variety of model-checking problems for nonflat systems under the light of parameterized complexity, taking the number of synchronized components as a parameter. We provide precise complexity measures (in the parameterized sense) for most of the problems we investigate, and evidence that the results are robust.     

Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction

The compaction problem is to partition the vertices of an input graph G onto the vertices of a fixed target graph H, such that adjacent vertices of G remain adjacent in H, and every vertex and non-loop edge of H is covered by some vertex and edge of G respectively, i.e., the partition is a homomorphism of G onto H (except the loop edges). Various computational complexity results, including both NP-completeness and polynomial time solvability, have been presented earlier for this problem for various classes of target graphs H. In this paper, we pay attention to the input graphs G, and present polynomial time algorithms for the problem for some class of input graphs, keeping the target graph H general as any reflexive or irreflexive graph. Our algorithms also give insight as for which instances of the input graphs, the problem could possibly be NP-complete for certain target graphs. With the help of our results, we are able to further refine the structure of the input graph that would be necessary for the problem to be possibly NP-complete, when the target graph is a cycle. Thus, when the target graph is a cycle, we enhance the class of input graphs for which the problem is polynomial time solvable. We also present analogous results for a variation of the compaction problem, which we call the vertex-compaction problem. Using our results, we also provide important relationships between compaction, retraction, and vertex-compaction to cycles.     

Sulla complessità di alcuni problemi di conteggio

This paper is intended to show that an algebraic approach can give useful suggestions to design efficient algorithms solving combinatorial problems. The problems we discusses in the paper are:

1. Counting strings of given length generated by a regular grammar. For this problem, we give an exact algorithm whose complexity is 0 (logn) (with respect to the number of executed operations), and an approximate algorithm which however still has the same order of complexity;
2. counting trees recognized by a tree automaton. For this problem, we give an exact algorithm of complexity 0(n) and an approximate one of complexity 0 (logn). For this approximate algorithm the relative error is shown to be 0 (1/n).

     

The mutual exclusion scheduling problem for permutation and comparability graphs

In this paper, we consider the mutual exclusion scheduling problem for comparability graphs. Given an undirected graph G and a fixed constant m, the problem is to find a minimum coloring of G such that each color is used at most m times. The complexity of this problem for comparability graphs was mentioned as an open problem by Möhring [Problem 9.10, in: I. Rival (Ed.), Graphs and Orders, Reidel, Dordrecht, 1985, p. 583] and for permutation graphs (a subclass of comparability graphs) as an open problem by Lonc [On complexity of some chain and antichain partition problem, in: G. Schmidt, R. Berghammer (Eds.), Graph Theoretical Concepts in Computer Science, WG 91, Lecture Notes in Computer Science, vol. 570, 1999, pp. 97–104]. We prove that this problem is already NP-complete for permutation graphs and for each fixed constant m⩾6.     

The complexity of constraint satisfaction problems for small relation algebras

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.     

A Method of Splitting Cochain Complexes for Computing Cohomology: Lie Algebra of Hamiltonian Vector Fields H(2|0)

Computation of homology or cohomology is inherently a problem of high combinatorial complexity. Recently, we have proposed a new algorithm for computing cohomology of Lie (super)algebras. This algorithm is based on splitting a complete cochain complex into minimal subcomplexes. The algorithm is implemented in C as a program LieCohomology. This paper presents results of computation of cohomology in a trivial module for a Lie algebra of Hamiltonian vector fields H(2|0). We demonstrate that the new approach is much more efficient than the traditional one. In particular, we have revealed some new cohomology classes for the H(2|0) algebra and the related Lie algebra of the Poisson vector fields Po(2|0).     

An effective and efficient approximate two-dimensional dynamic programming algorithm for supporting advanced computer vision applications

Dynamic programming is a popular optimization technique, developed in the 60’s and still widely used today in several fields for its ability to find global optimum. Dynamic Programming Algorithms (DPAs) can be developed in many dimension. However, it is known that if the DPA dimension is greater or equal to two, the algorithm is an NP complete problem. In this paper we present an approximation of the fully two-dimensional DPA (2D-DPA) with polynomial complexity. Then, we describe an implementation of the algorithm on a recent parallel device based on CUDA architecture. We show that our parallel implementation presents a speed-up of about 25 with respect to a sequential implementation on an Intel I7 CPU. In particular, our system allows a speed of about ten 2D-DPA executions per second for 85 × 85 pixels images. Experiments and case studies support our thesis.     

On the complexity of sandpile critical avalanches

In this work, we study The Abelian Sandpile Model from the point of view of computational complexity. We begin by studying the length distribution of sandpile avalanches triggered by the addition of two critical configurations: we prove that those avalanches are long on average, their length is bounded below by a constant fraction of the length of the longest critical avalanche which is, in most of the cases, superlinear. At the end of the paper we take the point of view of computational complexity, we analyze the algorithmic hardness of the problem consisting in computing the addition of two critical configurations, we prove that this problem is P complete, and we prove that most algorithmic problems related to The Abelian Sandpile Model are NC reducible to it.     

A Lagrangean relaxation based sensor deployment algorithm to optimize quality of service for target positioning

The target positioning service is one of useful applications for wireless sensor networks. So far, most papers considered traditional uniform quality of services (QoS) for target positioning in sensing fields. However, it is possible that all regions in a sensing field have different requirements for target positioning accuracy. We also concern the terrain of sensing fields might have some limitations for placing sensors. Therefore, this paper proposes a generic framework for the sensor deployment problem supporting differential quality of services (QoS) for target positioning to all regions in a sensing field. We define weighted error distance as metric of quality of positioning services. This problem is to optimize the QoS level for target positioning under the limitations of budget and discrimination priorities of regions, where locations and sensing radiuses of all sensors should be determined. We formulate the problem as a nonlinear integer programming problem where the objective function is to minimize of the maximum weighted error distance subject to the complete coverage, deployment budget, and discrimination priority constraints. A Lagrangean relaxation (LR) based heuristic is developed to solve the NP-hard problem. Experimental results reveal that the proposed framework can provide better quality of services for positioning than the previous researches, which only handles uniform QoS requirements. Moreover we evaluate the performance of proposed algorithm. As well as we adopt the previous algorithm, ID-CODE, as the benchmark to examine the proposed heuristic. The results show the proposed algorithm is very effective in terms of deployment cost.     

IPART: an automatic protocol reverse engineering tool based on global voting expert for industrial protocols

ABSTRACT

The industrial control system is an important part of many critical infrastructures and has a big influence on the security of them. With the rapid development of the industrial control system, there has been a significant increase for industrial control system to use the computer network, which has brought many security issues. Protocol security is one of the most important security issues. Many industrial protocols are unknown, which prevent firewall parsing and analysing network traffic, thus it brings a big challenge for intrusion detection, deep packet inspection and traffic management. One method to solve the problem is the reverse engineering technology. However, previous works are mainly for traditional network protocols and not very suitable for reversing industrial protocols. To address this problem, we propose IPART, an unsupervised tool for automatically reverse the format of the industrial protocol from network trace. IPART applies an extended voting expert algorithm to infer the boundaries of industrial protocol fields. Types of these fields are derived by statistical methods. It then classifies messages into sub-clusters by their field types and infers the format of each sub-cluster. Finally, IPART combines all results and gets the format tree of the protocol. We evaluate our work on three industrial protocols: Modbus, IEC104 and Ethernet/IP. Compared with some state-of-art approaches (lda model, Voting expert, netzob), our tool shows a better performance.

IPART reverse industrial protocols mainly by three stages. The tool firstly split raw packages into tokens and infer the fields of the protocol. Both fields property (offset, length, etc.) and semantic (length, transition id, etc.). It then class messages belong to the same format to a cluster and each cluster approximates a format. Finally, the tool combines all formats and get the protocol format tree.