Minimizing mean squared deviation of completion times with maximum tardiness constraint

We consider a nonpreemptive single-machine scheduling problem to minimize mean squared deviation of job completion times about a common due date with maximum tardiness constraint (MSD/T_max problem), where the common due date is large enough so that it does not constrain the minimization of MSD.The MSD/T_max problem is classified into three cases according to the value of maximum allowable tardiness Δ: Δ-unconstrained, Δ-constrained and tightly Δ-constrained cases. It is shown that the Δ-unconstrained MSD/T_max problem is equivalent to the unconstrained MSD problem and that the tightly Δ-constrained MSD/T_max problem with common due date d is equivalent to the tightly constrained MSD problem with common due date Δ. We also provide bounds to decide when the MSD/T_max problem is Δ-unconstrained or Δ-constrained. Then a solution procedure to the MSD/T_max problem is presented with several examples.     

Stock cutting to minimize cutting length

In this paper we investigate the following problem: Given two convex P_in, and P_out where P_in is completely contained in P_out, we wish to find a sequence of ‘guillotine cuts’ to cut out P_in from P_out such that the total length of the cutting sequence is minimized. This problem has applications in stock cutting where a particular shape or design (in this case the polygon P_in) needs to be cut out of a given piece of parent material (the polygon P_out) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improve the cutting time required per piece. We first prove some properties of the optimal solution to the problem and then give an approximation scheme for the problem that, given an error range δ, produces a cutting sequence whose total length is atmost δ more than that of the optimal cutting sequence. Then it is shown that this problem has optimal solutions that lie in the algebraic extension of the field that the input data belongs to — hence due to this algebraic nature of the problem, an approximation scheme is the best that can be achieved. Extensions of these results are also studied in the case where the polygons P_in and P_out are non-convex.     

Some properties of random walk paths

For random walk on the d-dimensional integer lattice we consider again the problem of deciding when a set is recurrent, that is visited infinitely often with probability one by the random walk in question. Some special cases are considered, among them the following: for d = 2, what sequences (n_j) have the property that with probability one the random walk visits the origin for infinitely many n_j. A related problem, which is however not a special case of the recurrence problem, is to decide for what sequences (n_j) the states visited by the random walk at times n_j are all distinct, with only a finite number of exceptions. This problem is dealt with in the final part of the paper.     

Optimal stopping for extremal processes

For an extremal process (Z_t)_t the optimal stopping problem for X_t = f(Z_t)?g(t) gives the continuous time analogue of the optimal stopping problem for max{Y₁,…,Y_k}?c_k where Y₁, Y₂,… are i.i.d. For the continuous time problem we derive optimal stopping times in explicit form and also show that the optimal stopping boundary is the limit of the optimal stopping boundaries for suitably standardized discrete problems.     

A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

On a boundary value problem for a higher-order elliptic equation

For an elliptic 2lth-order equation with constant (and only leading) real coefficients, we consider the boundary value problem in which the (k _j ? 1)st normal derivatives, j = 1,..., l, are specified, where 1 ≤ k ₁ < ... < k _l . If k _j = j, then it becomes the Dirichlet problem; and if k _j = j + 1, then it becomes the Neumann problem. We obtain a sufficient condition for this problem to be Fredholm and present a formula for the index of the problem.     

Complexity of a 3-dimensional assignment problem

We show that a certain 3-dimensional assignment problem is NP-complete. To do this we show that the following problem is NP-complete: given bipartite graphs G₁, G₂ with the same sets of vertices, do there exist perfect matchings M₁, M₂ of G₁, G₂ respectively such that M₁ ∩ M₂ =Ø?     

Problem with lacking Tricomi condition on a characteristic and an analog of the Frankl condition on a segment of the degeneration line for a class of mixed type equations

For the Gellerstedt equation with a singular coefficient, we consider a boundary value problem that differs from the Tricomi problem in that the boundary characteristic AC is arbitrarily divided into two parts AC ₀ and C ₀ C and the Tricomi condition is posed on the first of them, while the second part C ₀ C is free of boundary conditions. The lacking Tricomi condition is equivalently replaced by an analog of the Frankl condition on a segment of the degeneration line. The well-posedness of this problem is proved.     

The number of additional variables required for the integer programming formulation

It is known that a minimization problem having a finite feasible region with k elements can be formulated as an integer programming problem by introducing at most [log₂k] additional integer variables. In this note, we show that this bound is best possible in the sense that some minimization problem actually requires [log₂k] additional variables.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

On «bilocal» and periodicity problems for hyperbolic partial differential equations

The problem stated in the paper is to find solutions of equation (1) in the strip 0≤y≤a, and satisfying conditions (2), (3), α₁, α₁, α₂,z, δ andf being functions which satisfy suitable conditions. This problem is equivalent with that to find solutions of (4), (5). If δ=0, the problem is one of generalized periodicity. Theorem 1–3 give sufficient conditions for the existence of required solutions.     

Fuchsian systems with completely reducible monodromy

The solvability of the Riemann-Hilbert problem for representations χ = χ ₁ ⊕ χ ₂ having the form of a direct sum is considered. It is proved that any representation χ ₁ can be realized as a direct summand in the monodromy representation χ of a Fuchsian system. Other results are also obtained, which suggest a simple method for constructing counterexamples to the Riemann-Hilbert problem.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Complexity issues for the sandwich homogeneous set problem

Graph sandwich problems were introduced by Golumbic et al. (1994) in [12] for DNA physical mapping problems and can be described as follows. Given a property Π of graphs and two disjoint sets of edges E₁, E₂ with E₁⊆E₂ on a vertex set V, the problem is to find a graph G on V with edge set E_s having property Π and such that E₁⊆E_s⊆E₂.In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k≥2 in a graph and the problem of finding a sandwich homogeneous set of the same size k. Using this reduction, we prove that a number of natural (decision and counting) problems related to sandwich homogeneous sets are hard in general. We then exploit a little further the reduction and show that finding efficient algorithms to compute small sandwich homogeneous sets would imply substantial improvement for computing triangles in graphs.     

On the Minimum Sum Coloring of P 4-Sparse Graphs

In this paper, we study the minimum sum coloring (MSC) problem on P ₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P ₄-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P ₄-sparse graphs.     

Hierarchical location-allocation problems: A classification scheme

In the literature, the p-median problem has been well studied. For the p-median problem our objective is to locate p facilities among n(? p) locations such that the total weighted travel distance is minimized. In the problem formulation, it is tacitly assumed that the facilities are of one type.In many practical situations, systems that provide products/services generally consist of k( ? 2) distinct types of facilities. In such problems, we would like to locate p_i type i facilities, i = 1, 2, … k, among n ( ? Σ_i^k = ₁p_i) available locations. Here also our objective may be to locate these facilities such that the ‘total weighted travel distance’ is minimized. What makes these problems difficult and interesting is that the extension of the p-median problem formulation and solution procedures to these problems is not always obvious, easy or straightforward. The problem formulation and solution procedures depend upon the hierarchical relationship among the facility types and the flow of goods and services allowed among them.In this paper we attemp to classify the hierarchical location-allocation problems.     

Searching for an edge in a graph with restricted test sets

Consider the (2,n) group testing problem with test sets of cardinality at most 2. We determine the worst case number c₂ of tests for this restricted group testing problem.Furthermore, using a game theory approach we solve the generalization of this group testing problem to the following search problem, which was suggested by Aigner in [M. Aigner, Combinatorial Search, Wiley-Teubner, 1988]: Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with |X|≤2. What is the minimum number c₂(G) of questions, which are needed in the worst case to identify e?We derive sharp upper and lower bounds for c₂(G). We also show that the determination of c₂(G) is an NP-complete problem. Moreover, we establish some results on c₂ for random graphs.     

On packing and coloring hyperedges in a cycle

Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link e_j on the cycle is used at most c_j times, each hyperedge h_i has its profit p_i and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC).In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link e_j has same capacity k, we propose an algorithm with approximation ratio .