Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms

Due to their importance in industry and mathematical complexity, dynamic demand lot-sizing problems are frequently studied. In this article, we consider coordinated lot-size problems, their variants and exact and heuristic solutions approaches. The problem class provides a comprehensive approach for representing single and multiple items, coordinated and uncoordinated setup cost structures, and capacitated and uncapacitated problem characteristics. While efficient solution approaches have eluded researchers, recent advances in problem formulation and algorithms are enabling large-scale problems to be effectively solved. This paper updates a 1988 review of the coordinated lot-sizing problem and complements recent reviews on the single-item lot-sizing problem and the capacitated lot-sizing problem. It provides a state-of-the-art review of the research and future research projections. It is a starting point for anyone conducting research in the deterministic dynamic demand lot-sizing field.     

Single-machine batch delivery scheduling with an assignable common due window

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O(n⁸)$O(n^8)$ time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.     

Min-energy broadcast in mobile ad hoc networks with restricted motion

This paper concerns about energy-efficient broadcasts in mobile ad hoc networks, yet in a model where each station moves on the plane with uniform rectilinear motion. Such restriction is imposed to discern which issues arise from the introduction of movement in the wireless ad hoc networks. Given a transmission range assignment for a set of n stations S, we provide an polynomial O(n ²)-time algorithm to decide whether a broadcast operation from a source station could be performed or not. Additionally, we study the problem of computing a transmission range assignment for S that minimizes the energy required in a broadcast operation. An O(n ³log?n)-time algorithm for this problem is presented, under the assumption that all stations have equally sized transmission ranges. However, we prove that the general version of such problem is NP-hard and not approximable within a (1?o(1))ln?n factor (unless NP?DTIME(n ^O(log?log?n))). We then propose a polynomial time approximation algorithm for a restricted version of that problem.     

Some variations on constrained minimum enclosing circle problem

Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows:

1. Computing k identical circles of minimum radius with centers on L, whose union covers all the points in P.
2. Computing the minimum radius circle centered on L that can enclose at least k points of P.
3. If each point in P is associated with one of the k given colors, then compute a minimum radius circle with center on L such that at least one point of each color lies inside it.

We propose three algorithms for Problem (i). The first one runs in O(nklogn) time and O(n) space. The second one is efficient where k?n; it runs in O(nlogn+nk+k ²log³ n) time and O(nlogn) space. The third one is based on parametric search and it runs in O(nlogn+klog⁴ n) time. For Problem (ii), the time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. For Problem (iii), our proposed algorithm runs in O(nlogn) time and O(n) space.     

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.     

Largest area convex hull of imprecise data based on axis-aligned squares

In recent years, more and more algorithms related to imprecise data have been proposed. Specifically, some algorithms on computing the maximum area convex hull are designed recently when the imprecise data are modeled as non-overlapping axis-aligned squares or as equal size squares. The time complexity of the best known algorithm based on non-overlapping axis-aligned squares is O(n ⁷). If the squares have equal size and can overlap, the time complexity of the best known algorithm is O(n ⁵). In this paper, we improve the former from O(n ⁷) to O(n ⁵) and improve the latter from O(n ⁵) to O(n ²). These results are obtained by exploiting the non-trivial geometric properties of the problems.     

Alignments with non-overlapping moves,inversions and tandem duplications in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) time

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n ³) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n ⁵) for general scoring schemes, O(n ⁴log n) for concave scoring schemes and O(n ⁴) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164.     

Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a ΠΣΠ polynomial. We first prove that the first problem is #P-hard and then devise a O ^?(3 ⁿ s(n)) upper bound for this problem for any polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O ^?(2 ⁿ ) for ΠΣΠ polynomials. We then design fully polynomial-time randomized approximation schemes for this problem for ΠΣ polynomials. On the negative side, we prove that, even for ΠΣΠ polynomials with terms of degree ≤2, the first problem cannot be approximated at all for any approximation factor ≥1, nor “weakly approximated” in a much relaxed setting, unless P=NP. For the second problem, we first give a polynomial time λ-approximation algorithm for ΠΣΠ polynomials with terms of degrees no more a constant λ≥2. On the inapproximability side, we give a n ^(1??)/2 lower bound, for any ?>0, on the approximation factor for ΠΣΠ polynomials. When terms in these polynomials are constrained to degrees ≤2, we prove a 1.0476 lower bound, assuming P≠NP; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.     

Faster algorithm to find anti-risk path between two nodes of an undirected graph

For a weighted 2-edge connected graph G=(V,E), we are to find a “minimum risk path” from source s to destination t. This is a shortest s?t path under the assumption that at most one edge on the path may be blocked. The fact that the edge is blocked is known only when we reach a site adjacent to the blocked edge. If n and m are the number of nodes and edges of G, then we show that this problem can be solved in O(n ²) time using only simple data structures. This is an improvement over the previous O(mn+n ²logn) time algorithm. Moreover, with use of more complicated data structures like Fibonacci Heaps and transmuters the time can be further reduced to O(m+nlogn).     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.     

RNA multiple structural alignment with longest common subsequences

In this paper, we present a new model for RNA multiple sequence structural alignment based on the longest common subsequence. We consider both the off-line and on-line cases. For the off-line case, i.e., when the longest common subsequence is given as a linear graph with n vertices, we first present a polynomial O(n ²) time algorithm to compute its maximum nested loop. We then consider a slightly different problem—the Maximum Loop Chain problem and present an algorithm which runs in O(n ⁵) time. For the on-line case, i.e., given m RNA sequences of lengths n, compute the longest common subsequence of them such that this subsequence either induces a maximum nested loop or the maximum number of matches, we present efficient algorithms using dynamic programming when m is small. This research is partially supported by EPSCOR Visiting Scholar's Program and MSU Short-term Professional Development Program.     

Enumerating the edge-colourings and total colourings of a regular graph

In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k?((k?1)!) ^n/2. Our proof is constructive and leads to a branching algorithm enumerating all the k-edge-colourings of a connected k-regular graph in time O ^?(((k?1)!) ^n/2) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O ^?(2 ^n/2)=O ^?(1.4143 ⁿ ) and polynomial space. This improves the running time of O ^?(1.5423 ⁿ ) of the algorithm due to Golovach et al. (Proceedings of WG 2010, pp. 39–50, 2010). We also show that the number of 4-total-colourings of a connected cubic graph is at most 3?2^3n/2. Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph.     

Likelihood‐Based Estimation of Latent Generalized ARCH Structures

GARCH models are commonly used as latent processes in econometrics, financial economics, and macroeconomics. Yet no exact likelihood analysis of these models has been provided so far. In this paper we outline the issues and suggest a Markov chain Monte Carlo algorithm which allows the calculation of a classical estimator via the simulated EM algorithm or a Bayesian solution in O(T) computational operations, where T denotes the sample size. We assess the performance of our proposed algorithm in the context of both artificial examples and an empirical application to 26 UK sectorial stock returns, and compare it to existing approximate solutions.     

A simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n ²logn) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n?n/logn. In this paper, we remove the concept of critical point, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis.     

The web proxy location problem in general tree of rings networks

The Web proxy location problem in general networks is an NP-hard problem. In this paper, we study the problem in networks showing a general tree of rings topology. We improve the results of the tree case in literature and get an exact algorithm with time complexity O(nhk), where n is the number of nodes in the tree, h is the height of the tree (the server is in the root of the tree), and k is the number of web proxies to be placed in the net. For the case of networks with a general tree of rings topology we present an exact algorithm with O(kn ²) time complexity.This research has been supported by NSF of China (No. 10371028) and the Educational Department grant of Zhejiang Province (No. 20030622).     

The Center Location Improvement Problem Under the Hamming Distance

In this paper, we consider the center location improvement problems under the sum-type and bottleneck-type Hamming distance. For the sum-type problem, we show that achieving an algorithm with a worst-case ratio of O(log |V|) is NP-hard, and for the bottleneck-type problem, we present a strongly polynomial algorithm.     

A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

The maximum leaf spanning tree (MLST) is a good candidate for constructing a virtual backbone in self-organized multihop wireless networks, but is practically intractable (NP-complete). Self-stabilization is a general technique that permits to recover from catastrophic transient failures in self-organized networks without human intervention. We propose a fully distributed self-stabilizing approximation algorithm for the MLST problem in arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed to approximate an MLST. It builds a solution whose number of leaves is at least 1/3 of the maximum possible in arbitrary graphs. The time complexity of our algorithm is O(n ²) rounds.     

FPT algorithms for Connected Feedback Vertex Set

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|??k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 ^O(k) n ^O(1)) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.     

The topology aware file distribution problem

We present theoretical results for large-file distribution on general networks of known topology (known link bandwidths and router locations). We show that the problem of distributing a file in minimum time is NP-hard in this model, and we give an O(logn) approximation algorithm, where n is the number of workstations that require the file. We also characterize our method as optimal amongst the class of “no-link-sharing” algorithms.     

Computing maximum upward planar subgraphs of single-source embedded digraphs

We show how to compute a maximum upward planar single-source subgraph of a single-source embedded DAG G _φ . We first show that finding a maximum upward planar subgraph of a single-source embedded digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes O(n ⁴) time in the worst case and O(n ³) time on average.