k圈图的最大Laplace分离度

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

广义de Bruijn有向图的k-元控制集

$G=(V, A)$ 表示一个有向图, 其中 $V$ 和 $A$ 分别表示有向图 $G$ 的点集和弧集。 对集合 $D_{k}\subseteq V(G)$, 如果对于任意点 $v\in V(G)$, 都存在 $k$ 个点 $u_{i}$, $1\leq i\leq k$ (可能存在某个 $u_{i}$ 和 $v$ 是同一点) 使得 $(u_{i},v)\in A(G)$, 则称 $D_{k}$ 是 $G$ 的一个 $k$-元控制集。 有向图 $G$ 的 $k$-元控制数 $\gamma_{\times k}(G)$ 是 $G$ 的最小 $k$-元控制集所含点的数目。 给出了广义 de Bruijn 有向图的 $k$-元控制数的新上界, 并且具体给出了构造广义 de Bruijn 有向图的 $k$-元控制集的方法。 此外, 对某些特殊的广义 de Bruijn 有向图, 通过构造其 $k$-元控制集, 进一步改进了它们 $k$-元控制数的上界。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有$k$种不同的产品,每一客户均需要$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有$k$个设施来为其提供$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于$k$-种产品设施选址问题,我们通常简写为$k$-PUFLP,其中,当所有设施建设费用为0时,记为$k$-PUFLPN。本文对$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当$k\geq 3$时分析算法将$k$-PUFLPN的近似比从$\frac{3k}{2}-1$提升到了$\frac{3k}{2}-\frac{3}{2}$。鲁棒$k$-种产品设施选址问题是指在该问题中,最多有$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒$k$-种产品选址问题建立模型,当$k\geq 3$,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用$k$-PUFLPN中最优整数解与最优分数解的关系,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

一般超图的张量谱性质

将一致超图的逆Perron值的概念推广到了一般超图上,并证明了超图G连通的充要条件为其逆Perron值大于0。同时给出了一般超图G的二分宽度、等周数、离心率基于逆Perron值的一些下界。最后,讨论了张量的可奇染色问题,得到非负对称弱不可约张量A可奇染色的充要条件为A的拉普拉斯张量和无符号拉普拉斯张量有相同的的谱。     

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。