LP-based approximation algorithms for capacitated facility location

In the capacitated facility location problem with hard capacities, we are given a set of facilities, ${\mathcal{F}}$ , and a set of clients ${\mathcal{D}}$ in a common metric space. Each facility i has a facility opening cost f _i and capacity u _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal{F}}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way.     

On some combinatorial questions in finite-dimensional spaces

Bounds are given for supinf∥Σ^p_i=1ν_i∥, where sup is taken over all set systems V₁,…, V_p of Rⁿ with 0∈∩^p_i=1convV_i and sup_v∈Vi∥ν∥?1 for i=1,…, p, and inf is taken over all possible choices ν_i∈V_i for i=1,…, p. Another similar problem is considered. The bounds are sharp.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

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.     

Second order BVPs with state dependent impulses via lower and upper functions

The paper deals with the following second order Dirichlet boundary value problem with p ∈ ? state-dependent impulses: z″(t) = f (t,z(t)) for a.e. t ∈ [0, T], z(0) = z(T) = 0, z′(τ _i +) ? z′(τ _i ?) = I _i (τ _i , z(τ _i )), τ _i = γ _i (z(τ _i )), i = 1,..., p. Solvability of this problem is proved under the assumption that there exists a well-ordered couple of lower and upper functions to the corresponding Dirichlet problem without impulses.     

Coloring some classes of mixed graphs

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i,x_j], c(x_i)≠c(x_j) and for every arc (x_p,x_q), c(x_p)<c(x_q). We will analyse the complexity status of this problem for some special classes of graphs.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

On the distributions of the form ∑i(δpi−δni)

We present some properties of the distributions of the form T=∑_i(δ_pi?δ_ni), with ∑_id(p_i,n_i)<∞, which arise in the 3-d Ginzburg–Landau problem studied by Bourgain, Brezis and Mironescu (C. R. Acad. Sci. Paris, Ser. I 331 (2000) 119–124). We show that there always exists an irreducible representation of T. We also extend a result of Smets (C. R. Acad. Sci. Paris, Ser. I 334 (2002) 371–374) which says that T is a measure iff T can be written as a finite sum of dipoles. To cite this article: A.C. Ponce, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

The failure of the Hardy inequality and interpolation of intersections

The main idea of this paper is to clarify why it is sometimes incorrect to interpolate inequalities in a “formal” way. For this we consider two Hardy type inequalities, which are true for each parameter α≠0 but which fail for the “critical” point α=0. This means that we cannot interpolate these inequalities between the noncritical points α=1 and α=?1 and conclude that it is also true at the critical point α=0. Why? An accurate analysis shows that this problem is connected with the investigation of the interpolation of intersections (N∩L _p(w₀), N∩L_p(w₁)), whereN is the linear space which consists of all functions with the integral equal to 0. We calculate theK-functional for the couple (N∩L _p(w₀),N∩L _p (w₁)), which turns out to be essentially different from theK-functional for (L _p(w₀), L_p(w₁)), even for the case whenN∩L _p(w_i) is dense inL _p(w_i) (i=0,1). This essential difference is the reason why the “naive” interpolation above gives an incorrect result.     

Blow-up properties for a degenerate parabolic system with nonlinear localized sources

In this paper, we investigate the initial-boundary problem of a degenerate parabolic system with nonlinear localized sources. We classify the blow-up solutions into global blow-up cases and single-point blow-up cases according to the values of m,n,p_i,q_i. Furthermore, we obtain the uniform blow-up profiles of solutions for the global blow-up case. Finally, we give some numerical examples to verify the results. These extend and generalize a recent work of one of the authors [L. Du, Blow-up for a degenerate reaction-diffusion systems with nonlinear localized sources, J. Math. Anal. Appl. 324 (2006) 304-320], which only considered uniform blow-up profiles under the special case p₁=p₂=0.     

Simultaneous estimation of gamma scale parameter under entropy loss: Bayesian approach

LetX ₁,...,X _p bep(≥ 2) independent random variables, where eachX _i has a gamma distribution withk _i andθ _i . The problem is to simultaneously estimatep gammar parametersθ _i under entropy loss where the parameters are believed priori. Hierarchical Bayes (HB) and empirical Bayes(EB) estimators are investigated. Next, computer simulation is studied to compute the risk percentage improvement of the HB, EB and the estimator of Dey et al.(1987) compared to MVUE ofθ.     

On minimizing the weighted number of late jobs in unit execution time open-shops

We study unit execution time open-shops with integer release dates. This paper shows that, in this environment, the minimum weighted number of late jobs can be computed in polynomial time by dynamic programming. The complexity status of the corresponding problem Om|p_ij=1,r_i|∑w_iU_i was unknown before.     

Representing the GCD as linear combination in non-PID rings

We prove the following fact: If finitely many elements p ₁,p ₂,…,p _n of a unique factorization domain are given such that the greatest common divisor of each pair (p _i ,p _j ) can be expressed as a linear combination of p _i and p _j , then the greatest common divisor of all the p _i ’s can also be expressed as a linear combination of p ₁,…,p _n . We prove an analogous statement in general commutative rings.     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

On a functional equation generalizing the class of semistable distributions

With ?(p),p≥0 the Laplace-Stieltjes transform of some infinitely divisible probability distribution, we consider the solutions to the functional equation ?(p-e ^?pβΠ _i=1 ^m ?^γi (c _i p) for somem≥1,c _i>0, γ _i >0,i=1., …,m, β ε ®. We supply its complete solutions in terms of semistable distributions (the ones obtained whenm=1). We then show how to obtain these solutions as limit laws (r → ∞) of normalized Poisson sums of iid samples when the Poisson intensity λ(r) grows geometrically withr.     

Chromatic numbers of the strong product of odd cycles

The problem of determining the chromatic numbers of the strong product of cycles is considered. A construction is given proving χ (G) = 2^p +1 for a product of p odd cycles of lengths at least 2^p +1. Several consequences are discussed. In particular, it is proved that the strong product of p factors has chromatic number at most 2^p +1 provided that each factor admits a homomorphism to sufficiently long odd cycle C_mi, m_i ≥ 2^p +1.     

Valuations, equimultiplicity and normal flatness

Let R be a regular noetherian local ring of dimension n≥2 and (R_i)≡R=R₀⊂R₁⊂R₂⊂?⊂R_i⊂? be a sequence of successive quadratic transforms along a regular prime ideal p of R (i.e if p_i is the strict transform of p in R_i, then p_i≠R_i, i≥0). We say that p is maximal for (R_i) if for every non-negative integer j≥0 and for every prime ideal q_j of R_j such that (R_i) is a quadratic sequence along q_j with p_j⊂q_j, we have p_j=q_j. We show that p is maximal for (R_i) if and only if V=∪_i≥0R_i/p_i is a valuation ring of dimension one. In this case, the equimultiple locus at p is the set of elements of the maximal ideal of R for which the multiplicity is stable along the sequence (R_i), provided that the series of real numbers given by the multiplicity sequence associated with V diverges. Furthermore, if we consider an ideal J of R, we also show that is normally flat along at the closed point if and only if the Hironaka’s character ν^∗(J,R) is stable along the sequence (R_i). This generalizes well known results for the case where p has height one (see [B.M. Bennett, On the characteristic functions of a local ring, Ann. of Math. Second Series 91 (1) (1970) 25-87]).     

TheH p corona theorem in analytic polyhedra

TheH ^p corona problem is the following: Letg ₁, ...,g _m be bounded holomorphic functions with 0<δ≤Σ‖g _i ‖. Can we, for anyH ^p function ?, findH ^p functionsu ₁, ...,u _m such that Σg _i u _i =?? It is known that the answer is affirmative in the polydisc, and the aim of this paper is to prove that it is in non-degenerate analytic polyhedra. To prove this, we construct a solution using a certain integral representation formula. TheH ^p estimate for the solution is then obtained by localization and some harmonic analysis results in the polydisc.     

Effectifs des diverses sequences de polyedres 3-valents convexes ayant moins de 11 faces et de polyedres sans face triangulaire ayant de 11 a 14 faces

A table is presented of various sequences of 3-valent convex polyhedra, a sequence being defined by p₃p₄???p_i??? where p_i is the number of faces with i edges. These sequences are given for polyhedra with 6, 7, 8, 9, 10 faces and the sequences where p₃=0 are given for polyhedra having 11, 12, 13, 14 faces. The number of polyhedra is also given for each sequence.     

Minmax subtree cover problem on cacti

Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) of a partition X={X₁,X₂,…,X_p} of V and a set T of p subtrees T₁,T₂,…,T_p, each T_i containing X_i so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. In this paper, we propose an O(p²n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.