Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

Knapsack with variable weights satisfying linear constraints

We introduce a variant of the knapsack problem, in which the weights of items are also variables but must satisfy a system of linear constraints, and the capacity of knapsack is given and known. We discuss two models: (1) the value of each item is given; (2) the value-to-weight ratio of each item is given. The goal is to determine the weight of each item, and to find a subset of items such that the total weight is no more than the capacity and the total value is maximized. We provide several practical application scenarios that motivate our study, and then investigate the computational complexity and corresponding algorithms. In particular, we show that if the number of constraints is a fixed constant, then both problems can be solved in polynomial time. If the number of constraints is an input, then we show that the first problem is NP-Hard and cannot be approximated within any constant factor unless \(\mathrm{P}= \mathrm{NP}\), while the second problem is NP-Hard but admits a polynomial time approximation scheme. We further propose approximation algorithms for both problems, and extend the results to multiple knapsack cases with a fixed number of knapsacks and identical capacities.     

The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

Fibrés de Green et Régularité des Graphes C 0-Lagrangiens Invariants par un Flot de Tonelli

In this article, we prove different results concerning the regularity of the C ⁰-Lagrangian invariant graphs of the Tonelli flows. For example :

Branch rings, thinned rings, tree enveloping rings

We develop the theory of “branch algebras”, which are infinite-dimensional associative algebras that are isomorphic, up to taking subrings of finite codimension, to a matrix ring over themselves. The main examples come from groups acting on trees. In particular, for every field % MathType!End!2!1! we contruct a % MathType!End!2!1! which

Lattice Points in Large Convex Bodies

 Denote by the number of points of the lattice in the “blown up” domain , where is a convex body in () whose boundary is smooth and has nonzero curvature throughout. It is proved that for every fixed

Lattice Points in Large Convex Bodies

 Denote by the number of points of the lattice in the “blown up” domain , where is a convex body in () whose boundary is smooth and has nonzero curvature throughout. It is proved that for every fixed

The complexity of approximating a nonlinear program

We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time.Our results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics—using a combinatorial argument to get a hardness result for a continuous optimization problem.     

Double bubbles in<Emphasis Type="Bold">S</Emphasis><Superscript>3</Superscript> and<Emphasis Type="Bold">H</Emphasis><Superscript>3</Superscript>

We prove the double bubble conjecture in the three-sphereS ³ and hyperbolic three-spaceH ³ in the cases where we can apply Hutchings theory:

Quasi-Elliptic Integrals and Periodic Continued Fractions

 In this report we detail the following story. Several centuries ago, Abel noticed that the well-known elementary integral

Nonoverlap of the star unfolding

The star unfolding of a convex polytope with respect to a pointx on its surface is obtained by cutting the surface along the shortest paths fromx to every vertex, and flattening the surface on the plane. We establish two main properties of the star unfolding:

Multiple Boundary Concentrating Solutions to Dirichlet Problem of Hénon Equation

Abstract  Let Ω be the unit ball centered at the origin in . We study the following problem

Note on the computational complexity ofj-radii of polytopes in ℝ n

We show that, for fixed dimensionn, the approximation of inner and outerj-radii of polytopes in ℝ ⁿ , endowed with the Euclidean norm, is in ℙ. Our method is based on the standard polynomial time algorithms for solving a system of polynomial inequalities over the reals in fixed dimension.     

Comonotone approximation with interpolation at the ends on an interval

Let a function f ∈ C[-1, 1], changes its monotonisity at the finite collection Y := {y1,… ,ys} of s points yi ∈ (-1, 1). For each n ≥ N(Y), we construct an algebraic polynomial Pn, of degree ≤ n, which is comonotone with f, that is changes its monotonisity at the same points yi as f, and |f(x)-Pn(x)|≤c(s)ω2(f,(√1-x2)/n), x∈[-1,1],where N(Y) is a constant depending only on Y, c(s) is a constant depending only on s and ω2 (f, t) is the second modulus of smoothness of f.     

Subdirect products of hereditary congruence lattices

A congruence lattice L of an algebra A is called power-hereditary if every 0-1 sublattice of Lⁿ is the congruence lattice of an algebra on Aⁿ for all positive integers n. Let A and B be finite algebras. We prove

The behavior of the free boundary near the fixed boundary for a minimization problem

We show that the free boundary ∂{u > 0}, arising from the minimizer(s) u, of the functional

On approximation algorithms for concave mixed-integer quadratic programming

Concave mixed-integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an \(\epsilon \)-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in \(1/\epsilon \), provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless \(\mathcal {P}=\mathcal {NP}\).     

Estimation of Exponential Sums over Primes in Short Intervals I

 Let and be the von Mangoldt function and M?bius function, respectively, x real and y“small” compared with x. This paper gives, for the first time, a non-trivial estimate of the sum

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday