Polynomial time approximation schemes and parameterized complexity

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.     

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.     

Optimization of a convex program with a polynomial perturbation

We consider the problem of minimizing a convex function plus a polynomial p over a convex body K. We give an algorithm that outputs a solution x whose value is within range_K(p) of the optimum value, where range_K(p)=sup_xKp(x)−inf_xKp(x). When p depends only on a constant number of variables, the algorithm runs in time polynomial in 1/, the degree of p, the time to round K and the time to solve the convex program that results by setting p=0.     

Feasible Operations and Applicative Theories Based on λη

We study a theory PTO(λη) of polynomial time computability on the type of binary strings (in the style of [6]), as embedded in full lambda calculus with total application and extensionality. We prove that the closed terms of (provable) type W → W are exactly the polynomial time operations. This answers a conjecture of Strahm [13].     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set Bof n black point and a set W of m white points in the plane (m = O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to MLC implies a C-approximation to the MLF problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set B of n black point and a set W of m white points in the plane (m=O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to Minimum Linear Classification implies a C-approximation to the Minimum Line Fitting problem. Nevertheless, we obtain an O(log _n )-factor algorithm for MLC and we also obtain an O(log _Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

This paper deals with the total weighted tardiness minimization with a common due date on a single machine. The best previous approximation algorithm for this problem was recently presented in [H. Kellerer, V.A. Strusevich, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date, Theoretical Computer Science 369 (2006) 230-238] by Kellerer and Strusevich. They proposed a fully polynomial time approximation scheme (FPTAS) of O((n⁶logW)/ε³) time complexity (W is the sum of weights, n is the number of jobs and ε is the error bound). For this problem, we propose a new approach to obtain a more effective FPTAS of O(n²/ε) time complexity. Moreover, a more effective and simpler dynamic programming algorithm is designed.     

An Ascending Chain Condition on Wedderburn Radicals

In this note we study the properties of Amitsur's example for Wedderburn radicals, introducing the concept of W _n -reduced rings. The theories of commutative ring and reduced ring are generalized to W _n -reduced rings. We characterize the W _n -reduced property and study properties of W _n -reduced rings. It is shown that the classes of semi-commutative rings, W _n -reduced rings, and 2-primal rings are in a strictly increasing order. We extend the class of W _n -reduced rings, observing various kinds of extensions containing classical quotient rings, polynomial rings, and power series rings.

Communicated by M. Ferrero.     

Representability and Specht problem for G-graded algebras

Let W be an associative PI-algebra over a field F of characteristic zero, graded by a finite group G. Let idG(W) denote the T-ideal of G-graded identities of W. We prove: 1. [G-graded PI-equivalence] There exists a field extension K of F and a finite-dimensional Z/2Z×G-graded algebra A over K such that idG(W)=idG(A^∗) where A^∗ is the Grassmann envelope of A. 2. [G-graded Specht problem] The T-ideal idG(W) is finitely generated as a T-ideal. 3. [G-graded PI-equivalence for affine algebras] Let W be a G-graded affine algebra over F. Then there exists a field extension K of F and a finite-dimensional algebra A over K such that idG(W)=idG(A).     

A kind of multiquadric quasi-interpolation operator satisfying any degree polynomial reproduction property to scattered data

In this paper, by virtue of using the linear combinations of the shifts of f(x) to approximate the derivatives of f(x) and Waldron’s superposition idea (2009), we modify a multiquadric quasi-interpolation with the property of linear reproducing to scattered data on one-dimensional space, such that a kind of quasi-interpolation operator L_r+1f has the property of r+1(r∈Z,r≥0) degree polynomial reproducing and converges up to a rate of r+2. There is no demand for the derivatives of f in the proposed quasi-interpolation L_r+1f, so it does not increase the orders of smoothness of f. Finally, some numerical experiments are shown to compare the approximation capacity of our quasi-interpolation operators with that of Wu-Schaback’s quasi-interpolation scheme and Feng-Li’s quasi-interpolation scheme.     

Two-agent scheduling to minimize the total cost

Two agents, each having his own set of jobs, compete to perform their own jobs on a common processing resource. Each job of the agents has a weight that specifies its importance. The cost of the first agent is the maximum weighted completion time of his jobs while the cost of the second agent is the total weighted completion time of his jobs. We consider the scheduling problem of determining the sequence of the jobs such that the total cost of the two agents is minimized. We provide a 2-approximation algorithm for the problem, show that the case where the number of jobs of the first agent is fixed is NP-hard, and devise a polynomial time approximation scheme for this case.     

Ein globales Ergebnis für Bifurkationsaufgaben mit schwach differenzierbaren Operatoren

In this paper we are dealing with positive linear functionals on W-algebras. We introduce the notion of a positive linear functional with ∑-property (see Definition 1.1). It is shown that each positive linear functional on a W-algebra possesses the ∑-property. This fact allows to give a short proof of UHLMANN's conjecture on unitary mixing in the state space of a W-algebra. In proving our main theorem (see Theorem 1.2.) we obtain some results on positive linear functionals and orthoprojections which are useful in other context, too.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

Topological and analytical properties of Sobolev bundles,I: The critical case

We study the interrelationship between topological and analytical properties of Sobolev bundles and describe some of their applications to variational problems on principal bundles. We in particular show that the category of Sobolev principal G-bundles of class W ^2,m/2 defined over M ^m is equivalent to the category of smooth principal G-bundles on M and give a characterization of the weak sequential closure of smooth principal G-bundles with prescribed isomorphism class. We also prove a topological compactness result for minimizing sequences of a conformally invariant Yang-Mills functional.      

On the order of projective curves

Here we prove the existence of several componentsW of the Hilbert scheme of curves inP ⁿ such that the generalC W has Hartshorne-Rao module with order equal to its diameter.     

Resolution trajectorielle et analyse numerique des equations differentielles stochastiques

Let (ξ_t) be the solution of the S.D.E. (E) of Section 1. Doss [3] has shown the existence of a difFerentiable function h and of a differentiate process parametrized by the process W,γ(W,t), such that: ξ_t = h(γ(W, t), W_t). For all continuous functions u, X_t is defined by: X_t = h(γ(u, t) u_t). We develop a scheme of approximation of X_t (Theorems 2-6 and 3-4). This scheme has th following properties:?

1)it does not explicitly involve γ or h; this property is crucial, because,generally, h is not explicitly known, and its numerical approximation would be costly.

2)it converges to X_t, provided that u has bounded quadratic variation.

3)for u = W, it coincides with a scheme proposed by Milshtein [6] for quadratic-mean approximation.

Further, we give an estimate of the error due to this scheme.     

Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the DIMANET/PECO Program of the European Union.Supported by a research fellowship of the Euler Institute for Discrete Mathematics and its Applications. This research was done while Gerhard Woeginger was with the Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands.     

Approximations for Steiner Trees with Minimum Number of Steiner Points

Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.     

High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

Exact solution to a Lindley-type equation on a bounded support

We derive the limiting waiting-time distribution F_W of a model described by the Lindley-type equation W=max{0,B-A-W}, where B has a polynomial distribution. This exact solution is applied to derive approximations of F_W when B is generally distributed on a finite support. We provide error bounds for these approximations.