An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Flattening topologically spherical surface

The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem.     

Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities

In this paper, we consider the fire scheduling problem (FSP) for field artillery, which is the problem of scheduling operations of firing at given targets with a given set of weapons. We consider a situation in which the number of available weapons is smaller than the number of targets, the targets are assigned to the weapons already, and targets may move and hence the probability that a target is destroyed by a firing attack decreases as time passes. We present a branch and bound algorithm for the FSP with the objective of minimizing total threat of the targets, which is expressed as a function of the destruction probabilities of the targets. Results of computational tests show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time.     

Priority algorithms for the subset-sum problem

Greedy algorithms are simple, but their relative power is not well understood. The priority framework (Borodin et al. in Algorithmica 37:295–326, 2003) captures a key notion of “greediness” in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions, for which the accepted data items can be later rejected to maintain the feasibility of the solution. We first provide a tight bound of α≈0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β≈0.780 and γ≈0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ≈0.893. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS 4598, pp. 504–514.     

A refined algorithm for maximum independent set in degree-4 graphs

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.     

A BRANCH AND BOUND PROCEDURE FOR SETUP PROBLEMS IN FLEXIBLE MANUFACTURING SYSTEMS

We address a medium- to short-term production planning problem in a flexible manufacturing environment. First we present a single-machine, mixed integer programming model for part type selection and lot-sizing problems over a T-period planning horizon. Demand for part types changes dynamically through the periods. The objective is to meet the demand for part types during the periods they are demanded. Available machine time and tool magazine capacities are the system constraints in our models. We next extend on the single- machine model to include multiple machines. In addition to part type selection and lotsizing decisions, the extended model also addresses the machine-loading decision. We present exact branch and bound procedures based on linear programming relaxations for the two models. We also report the results of our computational experiments.     

Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

The use of demand information in selecting production plans and schedules

The strategic problem of selecting a production plan for a given planning horizon is usually treated as independent of the tactical problem of scheduling the production plan. This paper approaches both selecting the production plan and scheduling it as one problem. The problem is formulated as a zero-one integer program. The formulation accommodates many real-life considerations. The integer program is solved using a branch and bound procedure which provides the optimal production plan and schedule as well as the importance indices of the orders, a concept which is introduced and used in this study to rank the available orders within the planning horizon according to their importance to the firm. The integer program and the search procedure can be used as a decision supporting tool to respond to any changes in the demand information, capacity of the firm, or its operating strategy, and it guarantees the selection of feasible production plan(s) and optimal schedules.     

Combinatorics of TCP reordering

We study a combinatorial problem motivated by a receiver-oriented model of TCP traffic from Istrate et al. (2006), that incorporates information on both arrival times, and the dynamics of packet IDs. An important component of this model is a many-to-one mapping FB from sequences of IDs into a sequence of buffer sizes. We show that: i) Given a buffer sequence B, constructing a sequence A of IDs that belongs to the preimage of B is no harder than finding matchings in bipartite graph. ii) Counting the number of sequences A of packet IDs that belong to the preimage of B can be done in linear time in the special case when there exists a constant upper bound on the maximum entry in B. iii) This problem also has a fully polynomial randomized approximation scheme when we have a constant upper bound on the number of repeats in the packet sequences in the preimage. We also provide experimental evidence that the two previous results suffice to efficiently count the number of preimages for buffer sequences observed in real TCP data.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

SOLUTION OF THE SHORTEST ROUTE PROBLEM USING THE ASSIGNMENT TECHNIQUE

A solution to the shortest route problem of going from city i to city j with p necessary intermediate stops (0 p n - 2) is given using the assignment algorithm, with a simple modification of the initial matrix. A branch and bound algorithm is necessary in all but the simplest case (p = 0).     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

Preemptive Machine Covering on Parallel Machines

This paper investigates the preemptive parallel machine scheduling to maximize the minimum machine completion time. We first show the off-line version can be solved in O(mn) time for general m-uniform-machine case. Then we study the on-line version. We show that any randomized on-line algorithm must have a competitive ratio m for m-uniform-machine case and ∑_{i = 1}^m1/i for m-identical-machine case. Lastly, we focus on two-uniform-machine case. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the on-line problem for every machine speed ratio s≥ 1. We further consider the case that idle time is allowed to be introduced in the procedure of assigning jobs and the objective becomes to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the problem for every s≥ 1. We show that randomization does not help.     

Empirical Limits for Time Series Econometric Models

This paper characterizes empirically achievable limits for time series econometric modeling and forecasting. The approach involves the concept of minimal information loss in time series regression and the paper shows how to derive bounds that delimit the proximity of empirical measures to the true probability measure (the DGP) in models that are of econometric interest. The approach utilizes joint probability measures over the combined space of parameters and observables and the results apply for models with stationary, integrated, and cointegrated data. A theorem due to Rissanen is extended so that it applies directly to probabilities about the relative likelihood (rather than averages), a new way of proving results of the Rissanen type is demonstrated, and the Rissanen theory is extended to nonstationary time series with unit roots, near unit roots, and cointegration of unknown order. The corresponding bound for the minimal information loss in empirical work is shown not to be a constant, in general, but to be proportional to the logarithm of the determinant of the (possibility stochastic) Fisher–information matrix. In fact, the bound that determines proximity to the DGP is generally path dependent, and it depends specifically on the type as well as the number of regressors. For practical purposes, the proximity bound has the asymptotic form (K/2)log n, where K is a new dimensionality factor that depends on the nature of the data as well as the number of parameters in the model. When ‘good’ model selection principles are employed in modeling time series data, we are able to show that our proximity bound quantifies empirical limits even in situations where the models may be incorrectly specified. One of the main implications of the new result is that time trends are more costly than stochastic trends, which are more costly in turn than stationary regressors in achieving proximity to the true density. Thus, in a very real sense and quantifiable manner, the DGP is more elusive when there is nonstationarity in the data. The implications for prediction are explored and a second proximity theorem is given, which provides a bound that measures how close feasible predictors can come to the optimal predictor. Again, the bound has the asymptotic form (K/2)log n, showing that forecasting trends is fundamentally more difficult than forecasting stationary time series, even when the correct form of the model for the trends is known.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

An exact semidefinite programming approach for the max-mean dispersion problem

This paper proposes an exact algorithm for the Max-Mean dispersion problem (\(Max-Mean DP\)), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve \(Max-Mean DP\) instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches.