Objective Bayesian analysis for a capture–recapture model

In this paper, we study a special capture–recapture model, the $M_t$ model, using objective Bayesian methods. The challenge is to find a justified objective prior for an unknown population size $N$ . We develop an asymptotic objective prior for the discrete parameter $N$ and the Jeffreys’ prior for the capture probabilities $\varvec{\theta }$ . Simulation studies are conducted and the results show that the reference prior has advantages over ad-hoc non-informative priors. In the end, two real data examples are presented.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

Approximation algorithms for k-partitioning problems with partition matroid constraint

The $k$ -partitioning problem with partition matroid constraint is to partition the union of $k$ given sets of size $m$ into $m$ sets such that each set contains exactly one element from each given set. With the objective of minimizing the maximum load, we present an efficient polynomial time approximation scheme (EPTAS) for the case where $k$ is a constant and a full polynomial time approximation scheme (FPTAS) for the case where $m$ is a constant; with the objective of maximizing the minimum load, we present a $\frac{1}{k-1}$ -approximation algorithm for the general case, an EPTAS for the case where $k$ is a constant; with the objective of minimizing the $l_p$ -norm of the load vector, we prove that the layered LPT algorithm (Wu and Yao in Theor Comput Sci 374:41–48, 2007) is an all-norm 2-approximation algorithm.     

Weak Fenchel and weak Fenchel-Lagrange conjugate duality for nonconvex scalar optimization problems

In this work, by using weak conjugate maps given in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), weak Fenchel conjugate dual problem, ${(D_F^w)}$ , and weak Fenchel Lagrange conjugate dual problem ${(D_{FL}^w)}$ are constructed. Necessary and sufficient conditions for strong duality for the ${(D_F^w)}$ , ${(D_{FL}^w)}$ and primal problem are given. Furthermore, relations among the optimal objective values of dual problem constructed by using Augmented Lagrangian in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), ${(D_F^w)}$ , ${(D_{FL}^w)}$ dual problems and primal problem are examined. Lastly, necessary and sufficient optimality conditions for the primal and the dual problems ${(D_F^w)}$ and ${(D_{FL}^w)}$ are established.     

From submodule categories to preprojective algebras

Let \(S(n)\) be the category of invariant subspaces of nilpotent operators with nilpotency index at most \(n\) . Such submodule categories have been studied already in 1934 by Birkhoff, they have attracted a lot of attention in recent years, for example in connection with some weighted projective lines (Kussin, Lenzing, Meltzer). On the other hand, we consider the preprojective algebra \(\Pi _n\) of type \(\mathbb {A}_n\) ; the preprojective algebras were introduced by Gelfand and Ponomarev, they are now of great interest, for example they form an important tool to study quantum groups (Lusztig) or cluster algebras (Geiss, Leclerc, Schröer). We are going to discuss the connection between the submodule category \(\mathcal {S}(n)\) and the module category \(\hbox {mod}\;\Pi _{n-1}\) of the preprojective algebra \(\Pi _{n-1}\) . Dense functors \(\mathcal {S}(n) \rightarrow \hbox {mod}\;\Pi _{n-1}\) are known to exist: one has been constructed quite a long time ago by Auslander and Reiten, recently another one by Li and Zhang. We will show that these two functors are full, dense, objective functors with index \(2n\) , thus \(\hbox {mod}\;\Pi _{n-1}\) is obtained from \(\mathcal {S}(n)\) by factoring out an ideal which is generated by \(2n\) indecomposable objects. As a byproduct we also obtain new examples of ideals in triangulated categories, namely ideals \(\mathcal {I}\) in a triangulated category \(\mathcal {T}\) which are generated by an idempotent such that the factor category \(\mathcal {T}/\mathcal {I}\) is an abelian category.     

Construction of relative difference sets and Hadamard groups

‘There exist normal \((2m,2,2m,m)\) relative difference sets and thus Hadamard groups of order \(4m\) for all \(m\) of the form $$\begin{aligned} m= x2^{a+t+u+w+\delta -\epsilon +1}6^b 9^c 10^d 22^e 26^f \prod _{i=1}^s p_i^{4a_i} \prod _{i=1}^t q_i^2 \prod _{i=1}^u \left( (r_i+1)/2)r_i^{v_i}\right) \prod _{i=1}^w s_i \end{aligned}$$ under the following conditions: \(a,b,c,d,e,f,s,t,u,w\) are nonnegative integers, \(a_1,\ldots ,a_r\) and \(v_1,\ldots ,v_u\) are positive integers, \(p_1,\ldots ,p_s\) are odd primes, \(q_1,\ldots ,q_t\) and \(r_1,\ldots ,r_u\) are prime powers with \(q_i\equiv 1\ (\mathrm{mod}\ 4)\) and \(r_i\equiv 1\ (\mathrm{mod}\ 4)\) for all \(i, s_1,\ldots ,s_w\) are integers with \(1\le s_i \le 33\) or \(s_i\in \{39,43\}\) for all \(i, x\) is a positive integer such that \(2x-1\) or \(4x-1\) is a prime power. Moreover, \(\delta =1\) if \(x>1\) and \(c+s>0, \delta =0\) otherwise, \(\epsilon =1\) if \(x=1, c+s=0\) , and \(t+u+w>0, \epsilon =0\) otherwise. We also obtain some necessary conditions for the existence of \((2m,2,2m,m)\) relative difference sets in partial semidirect products of \(\mathbb{Z }_4\) with abelian groups, and provide a table cases for which \(m\le 100\) and the existence of such relative difference sets is open.     

Logarithmic Expansions and the Stability of Periodic Patterns of Localized Spots for Reaction–Diffusion Systems in {\mathbb {R}}^2

The linear stability of steady-state periodic patterns of localized spots in \({\mathbb {R}}^2\) for the two-component Gierer–Meinhardt (GM) and Schnakenberg reaction–diffusion models is analyzed in the semi-strong interaction limit corresponding to an asymptotically small diffusion coefficient \({\displaystyle \varepsilon }^2\) of the activator concentration. In the limit \({\displaystyle \varepsilon }\rightarrow 0\) , localized spots in the activator are centered at the lattice points of a Bravais lattice with constant area \(|\Omega |\) . To leading order in \(\nu ={-1/\log {\displaystyle \varepsilon }}\) , the linearization of the steady-state periodic spot pattern has a zero eigenvalue when the inhibitor diffusivity satisfies \(D={D_0/\nu }\) for some \(D_0\) independent of the lattice and the Bloch wavevector \({\pmb k}\) . From a combination of the method of matched asymptotic expansions, Floquet–Bloch theory, and the rigorous study of certain nonlocal eigenvalue problems, an explicit analytical formula for the continuous band of spectrum that lies within an \({\mathcal O}(\nu )\) neighborhood of the origin in the spectral plane is derived when \(D={D_0/\nu } + D_1\) , where \(D_1={\mathcal O}(1)\) is a detuning parameter. The periodic pattern is linearly stable when \(D_1\) is chosen small enough so that this continuous band is in the stable left half-plane \(\text{ Re }(\lambda )<0\) for all \({\pmb k}\) . Moreover, for both the Schnakenberg and GM models, our analysis identifies a model-dependent objective function, involving the regular part of the Bloch Green’s function, that must be maximized in order to determine the specific periodic arrangement of localized spots that constitutes a linearly stable steady-state pattern for the largest value of \(D\) . From a numerical computation, based on an Ewald-type algorithm, of the regular part of the Bloch Green’s function that defines the objective function, it is shown within the class of oblique Bravais lattices that a regular hexagonal lattice arrangement of spots is optimal for maximizing the stability threshold in \(D\) .     

On convex relaxations for quadratically constrained quadratic programming

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let $\mathcal{F }$ denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on $\mathcal{F }$ is dominated by an alternative methodology based on convexifying the range of the quadratic form $\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T$ for $x\in \mathcal{F }$ . We next show that the use of ?? $\alpha $ BB?? underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (??difference of convex??) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.     

On operator factorization of linear relations

Assume that $A$ and $B$ are two linear relations in certain linear spaces. The main objective of this note is to present two characterizations of the existence of two linear operators $C$ and $T$ such that $A = BC$ and $A = T\!B$ , respectively. These factorizations extend and complete some known results due to R.G. Douglas, Z. Sebestyén and D. Popovici.     

The Diederich–Fornaess index and the global regularity of the \bar{\partial }-Neumann problem

We describe along the guidelines of Kohn (Quantitative Estimates for Global Regularity. Analysis and Geometry in Several Complex Variables, pp. 97–128. Trend Math. Birkhäuser, Boston, 1999), the constant ${\mathcal {E}}_s$ which is needed to control the commutator of a totally real vector field $T_{{\mathcal {E}}}$ with $\bar{\partial }^*$ in order to have $H^s$ a-priori estimates for the Bergman projection $B_k, k\ge q-1$ , on a smooth $q$ -convex domain $D\subset \subset {\mathbb {C}}^{n}$ . This statement, not explicit in Kohn (Quantitative Estimates for Global Regularity. Analysis and Geometry in Several Complex Variables, pp. 97–128. Trend Math. Birkhäuser, Boston, 1999), yields regularity of $B_k$ in specific Sobolev degree $s$ . Next, we refine the pseudodifferential calculus at the boundary in order to relate, for a defining function $r$ of $D$ , the operators $(T^+)^{-\frac{\delta }{2}}$ and $(-r)^{\frac{\delta }{2}}$ . We are thus able to extend to general degree $k\ge 0$ of $B_k$ , the conclusion of (Quantitative Estimates for Global Regularity. Analysis and Geometry in Several Complex Variables, pp. 97–128. Trend Math. Birkhäuser, Boston, 1999) which only holds for $q=1$ and $k=0$ : if for the Diederich–Fornaess index $\delta $ of $D$ , we have $(1-\delta )^{\frac{1}{2}}\le {\mathcal {E}}_s$ , then $B_k$ is $H^s$ -regular.     

On the zeros of Meixner polynomials

We investigate the zeros of a family of hypergeometric polynomials $M_n(x;\beta ,c)=(\beta )_n\,{}_2F_1(-n,-x;\beta ;1-\frac{1}{c})$ , $n\in \mathbb N ,$ known as Meixner polynomials, that are orthogonal on $(0,\infty )$ with respect to a discrete measure for $\beta >0$ and $0<c<1.$ When $\beta =-N$ , $N\in \mathbb N $ and $c=\frac{p}{p-1}$ , the polynomials $K_n(x;p,N)=(-N)_n\,{}_2F_1(-n,-x;-N;\frac{1}{p})$ , $n=0,1,\ldots , N$ , $0<p<1$ are referred to as Krawtchouk polynomials. We prove results for the zero location of the orthogonal polynomials $M_n(x;\beta ,c)$ , $c<0$ and $n<1-\beta $ , the quasi-orthogonal polynomials $M_n(x;\beta ,c)$ , $-k<\beta <-k+1$ , $k=1,\ldots ,n-1$ and $0<c<1$ or $c>1,$ as well as the polynomials $K_{n}(x;p,N)$ with non-Hermitian orthogonality for $0<p<1$ and $n=N+1,N+2,\ldots $ . We also show that the polynomials $M_n(x;\beta ,c)$ , $\beta \in \mathbb R $ are real-rooted when $c\rightarrow 0$ .     

Online pricing for bundles of multiple items

Given a seller with $k$ types of items, $m$ of each, a sequence of users $\{u_1, u_2,\ldots \}$ arrive one by one. Each user is single-minded, i.e., each user is interested only in a particular bundle of items. The seller must set the price and assign some amount of bundles to each user upon his/her arrival. Bundles can be sold fractionally. Each $u_i$ has his/her value function $v_i(\cdot )$ such that $v_i(x)$ is the highest unit price $u_i$ is willing to pay for $x$ bundles. The objective is to maximize the revenue of the seller by setting the price and amount of bundles for each user. In this paper, we first show that a lower bound of the competitive ratio for this problem is $\Omega (\log h+\log k)$ , where $h$ is the highest unit price to be paid among all users. We then give a deterministic online algorithm, Pricing, whose competitive ratio is $O(\sqrt{k}\cdot \log h\log k)$ . When $k=1$ the lower and upper bounds asymptotically match the optimal result $O(\log h)$ .     

Sharp energy estimates for nonlinear fractional diffusion equations

We study the nonlinear fractional equation $(-\Delta )^su=f(u)$ in $\mathbb R ^n,$ for all fractions $0<s<1$ and all nonlinearities $f$ . For every fractional power $s\in (0,1)$ , we obtain sharp energy estimates for bounded global minimizers and for bounded monotone solutions. They are sharp since they are optimal for solutions depending only on one Euclidian variable. As a consequence, we deduce the one-dimensional symmetry of bounded global minimizers and of bounded monotone solutions in dimension $n=3$ whenever $1/2\le s<1$ . This result is the analogue of a conjecture of De Giorgi on one-dimensional symmetry for the classical equation $-\Delta u=f(u)$ in $\mathbb R ^n$ . It remains open for $n=3$ and $s<1/2$ , and also for $n\ge 4$ and all $s$ .     

Optimality conditions for weak {\psi} -sharp minima in vector optimization problems

In this paper, we develop the characterization of weak ${\psi}$ -sharp minimizer by means of an oriented distance function and investigate the weak ${\psi}$ -sharp minimizer of the composition of two functions. Moreover, we establish sufficient conditions of the weak ${\psi_1}$ -sharp and ${\psi_2}$ -sharp Pareto minimality for vector optimization problem with strictly differentiable and twice strictly differentiable objective function, respectively. Our results extend the corresponding ones in the literature.     

Geodesics,distance, and the CAT(0) property for the manifold of Riemannian metrics

Let $\mathcal F ^a_\lambda $ be the PBW degeneration of the flag varieties of type $A_{n-1}$ . These varieties are singular and are acted upon with the degenerate Lie group $SL_n^a$ . We prove that $\mathcal F ^a_\lambda $ have rational singularities, are normal and locally complete intersections, and construct a desingularization $R_\lambda $ of $\mathcal F ^a_\lambda $ . The varieties $R_\lambda $ can be viewed as towers of successive $\mathbb{P }^1$ -fibrations, thus providing an analogue of the classical Bott–Samelson–Demazure–Hansen desingularization. We prove that the varieties $R_\lambda $ are Frobenius split. This gives us Frobenius splitting for the degenerate flag varieties and allows to prove the Borel–Weil type theorem for $\mathcal F ^a_\lambda $ . Using the Atiyah–Bott–Lefschetz formula for $R_\lambda $ , we compute the $q$ -characters of the highest weight $\mathfrak sl _n$ -modules.     

Identification of a convolution kernel in a control problem for the heat equation with a boundary memory term

We consider the evolution of the temperature \(u\) in a material with thermal memory characterized by a time-dependent convolution kernel \(h\) . The material occupies a bounded region \(\Omega \) with a feedback device controlling the external temperature located on the boundary \(\Gamma \) . Assuming both \(u\) and \(h\) unknown, we formulate an inverse control problem for an integrodifferential equation with a nonlinear and nonlocal boundary condition. Existence and uniqueness results of a solution to the inverse problem are proved.     

Preemptive and non-preemptive generalized min sum set cover

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given $n$ ground elements and a collection of sets $\mathcal{S }= \{S_1, S_2, \ldots , S_m\}$ where each set $S_i \in 2^{[n]}$ has a positive requirement $\kappa (S_i)$ that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set $S_i$ is defined as the first index $j$ in the ordering such that the first $j$ elements in the ordering contain $\kappa (S_i)$ elements in $S_i$ . This problem was introduced by Azar et al. (2009) with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known by Bansal et al. (2010) and Skutella and Williamson (Oper Res Lett 39(6):433–436, 2011). We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set $S$ is covered in the moment when $\kappa (S)$ amount of elements in $S$ are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming relaxation and analysis are completely different from the aforementioned previous works. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved $12.4$ -approximation for the non-preemptive problem.     

Diophantine approximation with sign constraints

Let $\alpha $ and $\beta $ be real numbers such that $1$ , $\alpha $ and $\beta $ are linearly independent over $\mathbb {Q}$ . A classical result of Dirichlet asserts that there are infinitely many triples of integers $(x_0,x_1,x_2)$ such that $|x_0+\alpha x_1+\beta x_2| < \max \{|x_1|,|x_2|\}^{-2}$ . In 1976, Schmidt asked what can be said under the restriction that $x_1$ and $x_2$ be positive. Upon denoting by $\gamma \cong 1.618$ the golden ratio, he proved that there are triples $(x_0,x_1,x_2) \in \mathbb {Z}^3$ with $x_1,x_2>0$ for which the product $|x_0 + \alpha x_1 + \beta x_2| \max \{|x_1|,|x_2|\}^\gamma $ is arbitrarily small. Although Schmidt later conjectured that $\gamma $ can be replaced by any number smaller than $2$ , Moshchevitin proved very recently that it cannot be replaced by a number larger than $1.947$ . In this paper, we present a construction of points $(1,\alpha ,\beta )$ showing that the result of Schmidt is in fact optimal. These points also possess strong additional Diophantine properties that are described in the paper.     

The Ubiquity of the Orders of Fractional Semifields of Even Characteristic

To each non-square integer \(2^{2N+1}\ge 2^5\) there correspond semifields \(D\) of order of \(2^{2N+1}\) that contain \(\text{ GF}(4)\) . Hence there exist affine planes for each non-square order \(2^{2N+1}\ge 2^{5}\) that contain subaffine planes of order \(2^2\) . Moreover, there also exists semifields \(D_1\) and \(D_2\) , with \(|D_1|= |D_2| =|D|\) such that \(D_1\) is commutative and \(D_2\) is non-commutative but neither \(D_1\) nor \(D_2\) contains \(\text{ GF}(4)\) .