Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

A note on <Emphasis Type="Italic">n</Emphasis>! modulo <Emphasis Type="Italic">p</Emphasis>

Let p be a prime, \(\varepsilon >0\) and \(0<L+1<L+N < p\). We prove that if \(p^{1/2+\varepsilon }< N <p^{1-\varepsilon }\), then

$$\begin{aligned} \#\{n!\,\,({\mathrm{mod}} \,p);\,\, L+1\le n\le L+N\} > c (N\log N)^{1/2},\,\, c=c(\varepsilon )>0. \end{aligned}$$

We use this bound to show that any \(\lambda \not \equiv 0\ ({\mathrm{mod}}\, p)\) can be represented in the form \(\lambda \equiv n_1!\cdots n_7!\ ({\mathrm{mod}}\, p)\), where \(n_i=o(p^{11/12})\). This refines the previously known range for \(n_i\).

     

Cyclotomic Hecke Algebras of <Emphasis Type="Italic">G</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, <Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)

In this note, we find a monomial basis of the cyclotomic Hecke algebra \({\mathcal{H}_{r,p,n}}\) of G(r,p,n) and show that the Ariki-Koike algebra \({\mathcal{H}_{r,n}}\) is a free module over \({\mathcal{H}_{r,p,n}}\), using the Gröbner-Shirshov basis theory. For each irreducible representation of \({\mathcal{H}_{r,p,n}}\), we give a polynomial basis consisting of linear combinations of the monomials corresponding to cozy tableaux of a given shape.     

Lower semicontinuity and relaxation for integral functionals with <Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">x</Emphasis>)- and <Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">x,u</Emphasis>)-growth

We consider the questions of lower semicontinuity and relaxation for the integral functionals satisfying the p(x)- and p(x, u)-growth conditions. Presently these functionals are actively studied in the theory of elliptic and parabolic problems and in the framework of the calculus of variations. The theory we present rests on the following results: the remarkable result of Kristensen on the characterization of homogeneous p-gradient Young measures by their summability; the earlier result of Zhang on approximating gradient Young measures with compact support; the result of Zhikov on the density in energy of regular functions for integrands with p(x)-growth; on the author’s approach to Young measures as measurable functions with values in a metric space whose metric has integral representation.     

The <Emphasis Type="Italic">p</Emphasis>-harmonic approximation and the regularity of <Emphasis Type="Italic">p</Emphasis>-harmonic maps

We extend to the degenerate case , Simons approach to the classical regularity theory of harmonic maps of Schoen & Uhlenbeck, by proving a p-Harmonic Approximation Lemma. This allows to approximate functions with p-harmonic functions in the same way as the classical harmonic approximation lemma (going back to De Giorgi) does via harmonic functions. Finally, we show how to combine this tool with suitable regularity estimates for solutions to degenerate elliptic systems with a critical growth right hand side, in order to obtain partial -regularity of p-harmonic maps.Received: 2 November 2002, Accepted: 10 July 2003, Published online: 4 September 2003Mathematics Subject Classification (2000): 35J70, 49N60, 49Q60     

Cyclic Functions in <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>(<Emphasis Type="Bold">R</Emphasis>), 1 \le <Emphasis Type="Italic">p</Emphasis> < \infty

Functions whose translates span L ^p (R) are called L ^p-cyclic functions. For a fixed p \memb [1, \infty], we construct Schwartz-class functions which are L ^r -cyclic for r > p and not L ^r - cyclic for r \le p. We then construct Schwartz-class functions which are L ^r -cyclic for r \ge p and not L ^r -cyclic for r < p. The constructions differ for p \memb (1, 2) and p > 2.     

An Algorithm for Solving Capacitated Multicommodity <Emphasis Type="Italic">p</Emphasis>-median Transportation Problems

An algorithm for solving a special capacitated multicommodity p-median transportation problem (CMPMTP), which arises in container terminal management, is presented. There are some algorithms to solve similar kinds of problems. The formulation here is different from the existing modelling of the p-median or some related location problems. We extend the existing work by applying a Lagrangean relaxation to the CMPMTP. In order to obtain a satisfactory solution, a heuristic branch-and-bound algorithm is designed to search for a better solution, if one is possible. A comparison is also made with different algorithms.     

Kernels and <Emphasis Type="Italic">p</Emphasis>-Kernels of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">r</Emphasis></Superscript>-ary 1-Perfect Codes

The rank of a q-ary code C is the dimension of the subspace spanned by C. The kernel of a q-ary code C of length n can be defined as the set of all translations leaving C invariant. Some relations between the rank and the dimension of the kernel of q-ary 1-perfect codes, over as well as over the prime field , are established. Q-ary 1-perfect codes of length n=(q^m − 1)/(q − 1) with different kernel dimensions using switching constructions are constructed and some upper and lower bounds for the dimension of the kernel, once the rank is given, are established.Communicated by: I.F. Blake     

Influence of <Emphasis Type="Italic">M</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-supplemented subgroups on the structure of <Emphasis Type="Italic">p</Emphasis>-modular subgroups

A subgroup K of G is M _p -supplemented in G if there exists a subgroup B of G such that G = KB and TB < G for every maximal subgroup T of K with |K: T| = p ^α. We study the structure of the chief factor of G by using M _p -supplemented subgroups and generalize the results of Monakhov and Shnyparkov by involving the relevant results about the p-modular subgroup O ^p (G) of G.     

Spin-One <Emphasis Type="Italic">p</Emphasis>-Spin Glass: Exact Solution for Large <Emphasis Type="Italic">p</Emphasis>

We study the low-temperature properties of the p-spin spin glass model in the spin-one (three-state) case for large values of p. We show that the one-step replica symmetry-breaking phase is unstable at a very low temperature, and we calculate the explicit boundary of the stability interval, the Gardner temperature, analytically for large values of p. This temperature for the spin-one model has the same form of dependence on p as in the case of Ising spins (two states). In the one-step replica symmetrybreaking state, a quadrupolar orientational glass coexists with the spin glass and also with a regular quadrupole ordering.     

The classification of <Emphasis Type="Italic">p</Emphasis>-local finite groups over the extraspecial group of order <Emphasis Type="Italic">p</Emphasis><Superscript>3</Superscript> and exponent <Emphasis Type="Italic">p</Emphasis>

In this paper we classify the p-local finite groups over p¹⁺²₊, the extraspecial group of order p³ and exponent p for odd p. This study reduces to the classification of the saturated fusion systems over p¹⁺²₊, which will be characterized by the outer automorphism group, the number of -radical subgroups and the automorphism group of each nontrivial -radical subgroup. As part of this classification, we obtain three new exotic 7-local finite groups.Partially supported by MCYT grant BFM2001-2035.Partially supported by MCYT grant BFM2001-1825.Both authors have been supported by the EU grant nr HPRN-CT-1999-00119.in final form: 1 October 2003     

Continuous <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">p</Emphasis></Subscript>-symmetric distributions

For p > 0, the l _n,p -generalized surface measure on the l _n,p -unit sphere is studied and used for deriving a geometric measure representation for l _n,p -symmetric distributions having a density.     

Efficient <Emphasis Type="Italic">p</Emphasis>th root computations in finite fields of characteristic <Emphasis Type="Italic">p</Emphasis>

We present a method for computing pth roots using a polynomial basis over finite fields of odd characteristic p, p ≥ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension of our method requires p − 1 scalar multiplications of elements in by elements in . In addition, our method requires at most additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z ^1/p , defined as the Hamming weight of z ^1/p or , is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260–270, 2007) give is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find always.      

Hadamard variational formulas for <Emphasis Type="Italic">p</Emphasis>-torsion and <Emphasis Type="Italic">p</Emphasis>-eigenvalue with applications

In this paper, we pose two kinds of Minkowski problems involving the p-Laplacian operator. The Hadamard variational formulas for some p-Laplacian functionals are obtained. A good application is to prove symmetry results for solutions to some overdetermined problems of p-Laplacian equations.     

The classification of irreducible admissible mod <Emphasis Type="Italic">p</Emphasis> representations of a <Emphasis Type="Italic">p</Emphasis>-adic GL<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Let F be a finite extension of ℚ _p . Using the mod p Satake transform, we define what it means for an irreducible admissible smooth representation of an F-split p-adic reductive group over  [`( \mathbbF)]<sub>p</sub>\overline{ \mathbb{F}}_{p} to be supersingular. We then give the classification of irreducible admissible smooth GL <sub>n</sub> (F)-representations over  [`( \mathbbF)]_p\overline{ \mathbb{F}}_{p} in terms of supersingular representations. As a consequence we deduce that supersingular is the same as supercuspidal. These results generalise the work of Barthel–Livné for n=2. For general split reductive groups we obtain similar results under stronger hypotheses.     

Simultaneous approximation problems of <Emphasis Type="Italic">p</Emphasis>-adic numbers and <Emphasis Type="Italic">p</Emphasis>-adic knapsack cryptosystems - Alice in <Emphasis Type="Italic">p</Emphasis>-adic numberland

In this paper we construct the multi-dimensional p-adic approximation lattices by using simultaneous approximation problems (SAP) of p-adic numbers and we estimate the l _∞ norm of the p-adic SAP solutions theoretically by applying Dirichlet’s principle and numerically by using the LLL algorithm. By using the SAP solutions as private keys, the security of which depends on NP-hardness of SAP or the shortest vector problems (SVP) of p-adic lattices, we propose a p-adic knapsack cryptosystem with commitment schemes, in which the sender Alice prepares ciphertexts and the verification keys in her p-adic numberland.     

Approximation of sine-shaped functions by constants in the spaces <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>, <Emphasis Type="Italic">p</Emphasis> < 1

We investigate the best approximations of sine-shaped functions by constants in the spaces L_p for p < 1. In particular, we find the best approximation of perfect Euler splines by constants in the spaces L_p for certain p(0,1).Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 6, pp. 745–762, June, 2004.     

The mixed problem in <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> for some two-dimensional Lipschitz domains

We consider the mixed problem,