带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题,它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$,目的是在空间中寻找$k$个点作为中心集合$S$,使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广,本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取$（3+\alpha）k$个中心的情况下,可以达到$\beta$-近似,其中,参数$\alpha>34$,$\beta>\frac{\alpha+34}{\alpha-34}$。     

带惩罚μ-相似Bregman散度k-均值问题的初始化算法

$k$-均值问题是聚类中的经典问题,亦是NP-难问题。如果允许数据点不聚类,而是支付惩罚费用,则引出带惩罚的$k$-均值问题。本文将带惩罚的$k$-均值问题从欧氏距离推广到更一般的$\mu$-相似Bregman散度,研究了带惩罚$\mu$-相似Bregman散度$k$-均值问题的初始化算法。本文给出的初始化算法,近似比与$\mu$和数据点惩罚最大值与最小值的比例$r$相关。     

带惩罚μ-相似Bregman散度k-均值问题的初始化算法

$k$-均值问题是聚类中的经典问题,亦是NP-难问题。如果允许数据点不聚类,而是支付惩罚费用,则引出带惩罚的$k$-均值问题。本文将带惩罚的$k$-均值问题从欧氏距离推广到更一般的$\mu$-相似Bregman散度,研究了带惩罚$\mu$-相似Bregman散度$k$-均值问题的初始化算法。本文给出的初始化算法,近似比与$\mu$和数据点惩罚最大值与最小值的比例$r$相关。     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

DNA标号图和DNA计算

设$k\geq 2, 1\leq i \leq k$ 和 $\alpha \geq 1$是3个整数. 对任意一个由长为$k$的寡聚核苷酸组成的多重集, DNA标号图定义如下: 该多重集中的每个寡聚核苷酸作为一个顶点; 若一个顶点右端$i$个核苷酸与另一个顶点左端$i$个核苷酸相同, 则前一顶点控制后一顶点. 称有向图$D$是可$(k,i;\alpha)$标号的, 如果对$D$中的每个顶点$x$, 可设计一个$k$长的标号$(l_{1}(x),\ldots ,l_{k}(x)),$使得 对每一个$j\in \{1,\ldots,k\}$, $l_j(x)\in \{0,\ldots,\alpha-1\}$, 并且$(x,y)$是$D$中的一条弧当且仅当 $(l_{k-i+1}(x),\ldots,l_k(x))=(l_1(y),\ldots,l_i(y)).$ 由生物背景, 对一个有向图,若存在两个整数$k$和$i$, 使得它是可$(k,i;4)$标号的, 则它就是一个DNA标号图. 系统地研究了DNA标号图. 首先, 给出了它和一些已有图类之间的关系. 接着, 证明了对任意的DNA标号图,都存在一个正整数$i$, 使得它是可 $(2i,i;4)$标号的,这有利于DNA标号图的存储和操作. 此外, 还确定了最小的$i$, 并设计了一个多项式时间的算法对给定的DNA标号图进行$(2i,i;4)$标号. 最后, 在一个有$(2i,i;4)$标号的有向图上, 设计了一个DNA算法寻找给定两点间的所有路.     

关于模$p^\alpha$原根分布的推广

设$p$为奇素数,$\alpha$为任意大于$1$的整数,对于任意给定的正整数$k$, $k|p^\alpha-p^{\alpha-1}$,本文主要研究模$p^\alpha$的$k$次剩余的分布性质.     

从$A^{p}_{\alpha}$到$A^{\infty}(\varphi)$的加权复合算子

设$u \in H(D), \ \phi$为$D$上的解析自映射,定义$H(D)$上的加权复合算子为$u C_{\phi}(f)=$$uf\circ\phi$, \ $f\in H(D)$.本文得到了从$A^{p}_{\alpha}$到$A^{\infty}(\varphi)\ (A_{0}^{\infty}(\varphi))$的加权复合算子$u C_{\phi}$的有界性和紧性的充要条件.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

加权Dirichlet 空间上的一般Ces$\grave{a}$ro算子

对加权Dirichlet空间${\cal D}_{\alpha}=\left\{f\in H(D) ; ||f||_{{\cal D}_{\alpha}}^{2}=|f(0)|^{2}+\int_{D}|f'(z)|^{2}(1-|z|)^{\alpha}\d m(z)<+\infty \right\},~~-1<\alpha<+\infty,$我们研究了其上一般Ces$\grave{a}$ro算子的有界性. 此处$H(D)$表示复平面单位圆盘$D$上全纯函数的全体.     

平面内多连通区域的凸包定理和拟共形映射常数的估计

对平面$\mathbb{R}^2$内的任何多连通区域$\Omega$,设$S$是$\mathbb{R}^2 \backslash \Omega$在双曲空间$H^3$中凸包的边界. 若$\Omega$内的闭测地线的双曲长度存在一个正下界$l > 0$, 则从$S$到$\Omega$存在一个$K$拟共形映射,它保持$S$和$\Omega$的公共边界不动, 这里$K$仅依赖于$l$. 还将用参数$l$给出$K$的一个具体估计.     

Boundedness Characterization of Maximal Commutators on Orlicz Spaces in the Dunkl Setting

On the real line, the Dunkl operators$$D_{\nu}(f)(x):=\frac{d f(x)}{dx} + (2\nu+1) \frac{f(x) - f(-x)}{2x}, ~~ \quad\forall \, x \in \mathbb{R}, ~ \forall \, \nu \ge -\tfrac{1}{2}$$are differential-difference operators associated with the reflection group $\mathbb{Z}_2$ on $\mathbb{R}$, and on the $\mathbb{R}^d$ the Dunkl operators $\big\{D_{k,j}\big\}_{j=1}^{d}$ are the differential-difference operators associated with the reflection group $\mathbb{Z}_2^d$ on $\mathbb{R}^{d}$.In this paper, in the setting $\mathbb{R}$ we show that $b \in BMO(\mathbb{R},dm_{\nu})$ if and only if the maximal commutator $M_{b,\nu}$ is bounded on Orlicz spaces $L_{\Phi}(\mathbb{R},dm_{\nu})$. Also in the setting $\mathbb{R}^{d}$ we show that $b \in BMO(\mathbb{R}^{d},h_{k}^{2}(x) dx)$ if and only if the maximal commutator $M_{b,k}$ is bounded on Orlicz spaces $L_{\Phi}(\mathbb{R}^{d},h_{k}^{2}(x) dx)$.     

Fractional Hamiltonian systems with positive semi-definite matrix

We study the existence of solutions for the following fractional Hamiltonian systems $$ \left\{ \begin{array}{ll} - _tD^{\alpha}_{\infty}(_{-\infty}D^{\alpha}_{t}u(t))-\lambda L(t)u(t)+\nabla W(t,u(t))=0,\\[0.1cm] u\in H^{\alpha}(\mathbb{R},\mathbb{R}^n), \end{array} \right. ~~~~~~~~~~~~~~~~~(FHS)_\lambda $$ where $\alpha\in (1/2,1)$, $t\in \mathbb{R}$, $u\in \mathbb{R}^n$, $\lambda>0$ is a parameter, $L\in C(\mathbb{R},\mathbb{R}^{n^2})$ is a symmetric matrix, $W\in C^1(\mathbb{R} \times \mathbb{R}^n,\mathbb{R})$. Assuming that $L(t)$ is a positive semi-definite symmetric matrix, that is, $L(t)\equiv 0$ is allowed to occur in some finite interval $T$ of $\mathbb{R}$, $W(t,u)$ satisfies some superquadratic conditions weaker than Ambrosetti-Rabinowitz condition, we show that (FHS)$_\lambda$ has a solution which vanishes on $\mathbb{R}\setminus T$ as $\lambda \to \infty$, and converges to some $\tilde{u}\in H^{\alpha}(\R, \R^n)$. Here, $\tilde{u}\in E_{0}^{\alpha}$ is a solution of the Dirichlet BVP for fractional systems on the finite interval $T$. Our results are new and improve recent results in the literature even in the case $\alpha =1$.     

Thin equivalence relations in scaled pointclasses

For ordinals α beginning a Σ₁ gap in $\mathrm{L}(\mathbb {R})$, where $\Sigma _{1}^{\mathrm{J}_{\alpha }(\mathbb {R})}$ is closed under number quantification, we give an inner model‐theoretic proof that every thin $\Sigma _{1}^{\mathrm{J}_{\alpha }(\mathbb {R})}$ equivalence relation is $\Delta _{1}^{\mathrm{J}_{\alpha }(\mathbb {R})}$ in a real parameter from the (optimal) hypothesis $\mathsf {AD}^{\mathrm{J}_{\alpha }(\mathbb {R})}$.     

限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

Symmetric Markov chains on with unbounded range

We consider symmetric Markov chains on where we do not assume that the conductance between two points must be zero if the points are far apart. Under a uniform second moment condition on the conductances, we obtain upper bounds on the transition probabilities, estimates for exit time probabilities, and certain lower bounds on the transition probabilities. We show that a uniform Harnack inequality holds if an additional assumption is made, but that without this assumption such an inequality need not hold. We establish a central limit theorem giving conditions for a sequence of normalized symmetric Markov chains to converge to a diffusion on corresponding to an elliptic operator in divergence form.

     

On Poincaré-Friedrichs Type Inequalities for the Broken Sobolev Space ${\rm W}^{2,1}$

We are concerned with the derivation of Poincaré-Friedrichs type inequalities in the broken Sobolev space $W^{2,1}$($Ω$; $\mathcal{T}_h$) with respect to a geometrically conforming, simplicial triagulation $\mathcal{T}_h$ of a bounded Lipschitz domain $Ω$ in $\mathbb{R}^d$ , $d$ $∈$ $\mathbb{N}$. Such inequalities are of interest in the numerical analysis of nonconforming finite element discretizations such as ${\rm C}^0$ Discontinuous Galerkin (${\rm C}^0$${\rm DG}$) approximations of minimization problems in the Sobolev space $W^{2,1}$($Ω$), or more generally, in the Banach space $BV^2$($Ω$) of functions of bounded second order total variation. As an application, we consider a ${\rm C}^0$${\rm DG}$ approximation of a minimization problem in$BV^2$($Ω$) which is useful for texture analysis and management in image restoration.