An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) [6] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(logm)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. [6] and Thielen and Krumke (2008) [8], which have an approximation guarantee of O(m^2/3).     

Approximation of RNA multiple structural alignment

In the context of non-coding RNA (ncRNA) multiple structural alignment, Davydov and Batzoglou (2006) introduced in [7] the problem of finding the largest nested linear graph that occurs in a set G of linear graphs, the so-called Max-NLS problem. This problem generalizes both the longest common subsequence problem and the maximum common homeomorphic subtree problem for rooted ordered trees.In the present paper, we give a fast algorithm for finding the largest nested linear subgraph of a linear graph and a polynomial-time algorithm for a fixed number (k) of linear graphs. Also, we strongly strengthen the result of Davydov and Batzoglou (2006) [7] by proving that the problem is NP-complete even if G is composed of nested linear graphs of height at most 2, thereby precisely defining the borderline between tractable and intractable instances of the problem. Of particular importance, we improve the result of Davydov and Batzoglou (2006) [7] by showing that the Max-NLS problem is approximable within ratio in O(kn²) running time, where mopt is the size of an optimal solution. We also present O(1)-approximation of Max-NLS problem running in O(kn) time for restricted linear graphs. In particular, for ncRNA derived linear graphs, a -approximation is presented.     

Wall crossings for double Hurwitz numbers

Double Hurwitz numbers count covers of P¹ by genus g curves with assigned ramification profiles over 0 and ∞, and simple ramification over a fixed branch divisor. Goulden, Jackson and Vakil have shown double Hurwitz numbers are piecewise polynomial in the orders of ramification (Goulden et al., 2005) [10], and Shadrin, Shapiro and Vainshtein have determined the chamber structure and wall crossing formulas for g=0 (Shadrin et al., 2008) [15]. This paper gives a unified approach to these results and strengthens them in several ways — the most important being the extension of the results of Shadrin et al. (2008) [15] to arbitrary genus.The main tool is the authors? previous work (Cavalieri et al., 2010) [6] expressing double Hurwitz number as a sum over certain labeled graphs. We identify the labels of the graphs with lattice points in the chambers of certain hyperplane arrangements, which give rise to piecewise polynomial functions. Our understanding of the wall crossing for these functions builds on the work of Varchenko (1987) [17], and could have broader applications.     

A diffusion-type process with a given joint law for the terminal level and supremum at an independent exponential time

We construct a weak solution to the stochastic functional differential equation , where M_t=sup_0≤s≤tX_s. Using the excursion theory, we then solve explicitly the following problem: for a natural class of joint density functions μ(y,b), we specify σ(.,.), so that X is a martingale, and the terminal level and supremum of X, when stopped at an independent exponential time ξ_λ, is distributed according to μ. We can view (X_t∧ξλ) as an alternate solution to the problem of finding a continuous local martingale with a given joint law for the maximum and the drawdown, which was originally solved by Rogers (1993) [21] using the excursion theory. This complements the recent work of Carr (2009) [5] and Cox et al. (2010) [7], who consider a standard one-dimensional diffusion evaluated at an independent exponential time.¹     

On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two

In an article Cheng (2009) [3] published recently in this journal, it was shown that when k≥3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k=2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism, but no harder than graph isomorphism.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

The homotopy limit problem for Hermitian K-theory, equivariant motivic homotopy theory and motivic Real cobordism

The homotopy limit problem for Karoubi?s Hermitian K-theory (Karoubi, 1980) [26] was posed by Thomason (1983) [44]. There is a canonical map from algebraic Hermitian K-theory to the Z/2-homotopy fixed points of algebraic K-theory. The problem asks, roughly, how close this map is to being an isomorphism, specifically after completion at 2. In this paper, we solve this problem completely for fields of characteristic 0 (Theorems 16, 20). We show that the 2-completed map is an isomorphism for fields F of characteristic 0 which satisfy cd₂(F[i])<∞, but not in general.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. [H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30 000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.     

Matching signatures and Pfaffian graphs

Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four.     

A tabu search tutorial based on a real-world scheduling problem

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n ³) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).     

On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

Uniform well-posedness and inviscid limit for the Benjamin–Ono–Burgers equation

We prove that the Cauchy problem for the Benjamin–Ono–Burgers equation is uniformly globally well-posed in Hs (s?1) for all ε∈[0,1]. Moreover, we show that as ε→0 the solution converges to that of Benjamin–Ono equation in C([0,T]:Hs) (s?1) for any T>0. Our results give an alternative proof for the global well-posedness of the BO equation in H¹(R) without using gauge transform, which was first obtained by Tao (2004) [23], and also solve the problem addressed in Tao (2004) [23] about the inviscid limit behavior in H¹.     

Almost Lagrangian obstruction

The aim of this paper is to describe the obstruction for an almost Lagrangian fibration to be Lagrangian, a problem which is central to the classification of Lagrangian fibrations and, more generally, to understanding the obstructions to carry out surgery of integrable systems, an idea introduced in Zung (2003) [16]. It is shown that this obstruction (namely, the homomorphism D of Dazord and Delzant (1987) [4] and Zung (2003) [16]) is related to the cup product in cohomology with local coefficients on the base space B of the fibration. The map is described explicitly and some explicit examples are calculated, thus providing the first examples of non-trivial Lagrangian obstructions.     

Iterative character constructions for algebra groups

We construct a family of orthogonal characters of an algebra group which decompose the supercharacters defined by Diaconis and Isaacs (2008) [6]. Like supercharacters, these characters are given by nonnegative integer linear combinations of Kirillov functions and are induced from linear supercharacters of certain algebra subgroups. We derive a formula for these characters and give a condition for their irreducibility; generalizing a theorem of Otto (2010) [20], we also show that each such character has the same number of Kirillov functions and irreducible characters as constituents. In proving these results, we observe as an application how a recent computation by Evseev (2010) [7] implies that every irreducible character of the unitriangular group UTn(q) of unipotent n×n upper triangular matrices over a finite field with q elements is a Kirillov function if and only if n?12. As a further application, we discuss some more general conditions showing that Kirillov functions are characters, and describe some results related to counting the irreducible constituents of supercharacters.     

Moment vanishing problem and positivity: Some examples

We consider the problem of vanishing of the momentswith Ω a compact domain in Rn and P(x), q(x) complex polynomials in x∈Ω (MVP). The main stress is on relations of this general vanishing problem to the following conjecture which has been studied recently in Mathieu (1997) [22], Duistermaat and van der Kallen (1998) [17], Zhao (2010) [34] and [35] and in other publications in connection with the vanishing problem for differential operators and with the Jacobian conjecture:

Conjecture A. 

For positive μ ifmk(P,1)=0fork=1,2,… , thenmk(P,q)=0fork?1for any q.