教师简介

张鹏(教授,博导)

山东大学软件学院 --> 人工智能研究中心 --> 组合优化与算法实验室

山东大学软件学院 --> 机器学习与数据挖掘实验室


Peng ZHANG (Professor)

Laboratory of Combinatorial Optimization and Algorithms, Shandong University.

For my English homepage, please visit https://www.researchgate.net/profile/Peng-Zhang-155 .


欢迎来到我的主页。我于2007年7月在中科院软件所取得博士学位,现在山东大学软件学院工作,主要从事算法和计算理论方面的教学和科研工作。

C&A 2023:https://www.sc.sdu.edu.cn/info/1033/3997.htm


*** 研究领域 ***

理论计算机科学包含许多内容,算法和计算理论是其中一个重要的组成部分。给定一个计算模型(电子计算机是计算模型的一个具体例子),该模型能够解决什么样的问题?能够解决多难的问题?这多半是出于人们的好奇心。给定一个问题,如何设计算法解决该问题?算法求解的性能如何评价?解决该问题至少需要什么样的计算模型?这多半是人们觉得这样的问题“有用”。新的时代涌现新的科学问题,新的科学问题呼唤新的算法求解。因此,算法是一棵常青树。古往今来,知识就是在“有趣”和“有用”的双重推动下,不断创新,不断向前发展。


研究方向:算法设计与分析,组合最优化,计算复杂性。

教学:最优化方法(本科生),随机算法(研究生)。

https://www.view.sdu.edu.cn/info/1445/172678.htm


*** 博士硕士招生 ***

招收研究生从事算法和计算理论研究,以及相关软件设计与研发。

2024年可招收 1 名专业学位硕士研究生

2024年没有博士研究生招生计划。


*** 联系方式 ***

通讯地址:济南市舜华路1500号山东大学软件学院,邮政编码:250101

电子邮件:algzhang@sdu.edu.cn


*** 发表论文 ***

长期以来奋战在科研一线,以第一作者发表研究论文20余篇,共发表论文60余篇。论文主要发表在理论计算机科学领域的IANDC,Algorithmica,TCS,FCS,ToCS,DAM等顶级和主流国际期刊,以及LATIN,ISAAC,COCOON等主流国际会议上。

(1)DBLP论文列表请参阅:https://dblp.uni-trier.de/pid/21/1048-8.html。

(2)可在https://www.researchgate.net/profile/Peng-Zhang-155个人主页中下载(部分)已发表的论文。

(3)也可以点击此处在Google Scholar中查看我的论文列表。


*** 编著/著作 ***

(1)博士学位论文:《网络优化问题的近似算法》。PDF:https://www.researchgate.net/publication/367236482_Approximation_Algorithms_for_Network_Optimization_Problems_PhD_Thesis

(2)本科生教材:张鹏,最优化方法。科学出版社,2023年4月。京东:https://item.jd.com/13951126.html


*** 科研项目 ***

(9)主持,国家自然科学基金面上项目,《标签割问题的细粒度计算研究》,2023-2026。

(8)主持,国家自然科学基金面上项目,《网络科学中若干非线性组合优化问题的复杂性和算法》,2020-2023。

(7)主持,国家自然科学基金面上项目,《网络同质性原理和图划分问题的近似算法》,2017-2020。

(6)主持,山东省自然科学基金面上项目,《面向现代应用的网络最小割问题的近似算法与近似困难性研究》,2016-2019。

(5)主持,山东大学自主创新基金项目,《网络割集问题的近似算法及其应用》,2012-2014。

(4)主持,国家自然科学基金面上项目,《网络链路选择问题的近似算法》,2010-2012。

(3)主持,山东省博士后创新基金一等资助项目,《网络设计问题的近似算法设计与分析》,2009。

(2)主持,国家博士后基金特别资助项目,《多重割集问题的近似算法》,2009。

(1)主持,国家博士后基金面上项目,《网络割集问题的近似算法与近似难度》,2008。


*** 若干代表研究工作 ***

---------------------------------------

研究工作1:标签s-t割问题

(·)标签s-t割问题是来自系统安全、计算机网络等领域的一个优化问题,是经典的最小s-t割问题的推广。给一个图,边上有标签,该问题询问最小数目的标签,使得在图上去掉具有这些标签的边之后,能够断开给定的(s, t)顶点对。

(·)论文[ZCTZ11]使用贪心的技术,对该问题给出了近似比为m^{1/2}的近似算法。根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[ZCTZ11]已被引用25次。

(·)论文[TZ12]使用线性规划舍入的技术,对该问题给出了近似比为m^{1/2} / OPT^{1/2}的近似算法和近似比为n^{2/3} / OPT^{1/3}的近似算法。

(·)论文[ZFT18]使用纯组合的技术,对该问题给出了近似比为m^{1/2} / OPT^{1/2}的近似算法和近似比为n^{2/3} / OPT^{1/3}的近似算法。

(·)论文[ZT20]使用概率的方法,证明了标签s-t割问题的一个自然的线性规划的整性间隙至少为Omega(m^{1/3})。这意味着如果使用基于该规划的纯粹线性规划技术为标签s-t割问题设计近似算法,近似比不会好于O(m^{1/3})。学校报导:https://www.view.sdu.edu.cn/info/1021/132778.htm

(·)论文[Z20]对带权重的标签s-t割问题给出了首个以顶点数n表示近似比的近似算法,近似比为O(n^{2/3})。该论文的创新是一种将边上的权重同时解释为“长度”和“容量”的机制。这里的难点在于长度和容量是两个具有完全不同物理意义的量(若用水管举例,一个是长度,一个是截面积),它们在算法中的处理方法有很大的不同。


---------------------------------------

研究工作2:设施选址问题

(·)设施选址(Facility Location)是运筹学和组合优化中的一个经典的基础研究问题,和它密切相关的是k-Median问题。k-设施选择问题是设施选择问题和k-Median问题的综合和推广。

(·)论文[Z07a]使用局部搜索的方法,对经典的k-设施位置问题(k-Facility Location)给出了近似比为3.7321的近似算法,该结果改进了Kamal Jain等人(JACM)的近似比4。论文[Z07a]被组合优化领域的流行专著《Combinatorial Optimization: Theory and Algorithms》(Korte, Vygen著,Springer出版社,第5版,2012)引用。根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[Z07a]已被引用50次。


---------------------------------------

研究工作3:网络同质性相关问题的研究

(·)提出并研究了最大满意边问题和最大满意顶点问题。一条边,若其两个端点具有相同的颜色,则该边称为满意的。一个顶点,若其所有邻接边都是满意的,则该顶点称为满意的。给一个图,部分顶点已经着色,最大满意边问题寻找一种着色方案,使满意边的数目最多。类似地,最大满意顶点问题寻找一种着色方案,使满意顶点的数目最多。

(·)论文[ZXJ+18]使用线性规划随机舍入技术,对这两个问题分别给出了近似比为0.8535和1/Delta的近似算法。


---------------------------------------

研究工作4:非平衡割问题

(·)非平衡最小s-t割问题询问s一侧顶点数目不超过k的最小s-t割。论文[LZ10]对该问题给出了近似比为O(log n)的近似算法,论文[Z16]对该问题给出了近似比为O(k)的近似算法。

(·)非平衡最稀疏割(Sparsest Cut)问题询问一侧顶点数目不超过k的稀疏度最小的割。非平衡最小传导率(Min Conductance)问题询问一侧顶点数目不超过k的传导率最小的割。这两个问题来自于对社会网络的研究。论文[LZ13]对这两个问题给出了首个双准则近似算法。

(·)根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[LZ13]已被引用11次。


---------------------------------------

研究工作5:一类部分优化问题的通用近似算法

(·)若只要求完成优化问题总体目标的一部分,则该类问题称为部分优化问题。论文[ZZL12]设计了一种通用的近似算法,能够求解一类部分优化问题。特别地,使用该方法,对著名的k-施坦纳森林(k-Steiner Forest)问题给出了近似比为q^{1/2}的近似算法。该方法在论文[Z22]中进行了提炼和总结。


*** 若干代表论文 ***

[ZT20] Peng Zhang, Linqing Tang. 

Minimum label s-t cut has large integrality gaps. 

Information and Computation, 275:104543:1-104543:15, 2020.

PDF:https://arxiv.org/abs/1908.11491

学校报导:https://www.view.sdu.edu.cn/info/1021/132778.htm


[ZXJ+18] Peng Zhang, Yao Xu, Tao Jiang, Angsheng Li, Guohui Lin, Eiji Miyano.

Improved approximation algorithms for the maximum happy vertices and edges problems.

Algorithmica, 80(5):1412-1438, 2018.

PDF:https://www.researchgate.net/publication/315592738_Improved_Approximation_Algorithms_for_the_Maximum_Happy_Vertices_and_Edges_Problems


[ZFT18] Peng Zhang, Bin Fu, Linqing Tang.

Simpler and better approximation algorithms for the unweighted label s-t cut problem.

Algorithmica, 80(1):398-409, 2018.

PDF:https://www.researchgate.net/publication/311636268_Simpler_and_Better_Approximation_Algorithms_for_the_Unweighted_Minimum_Label_s-t_Cut_Problem


[Zha16] Peng Zhang.

A new approximation algorithm for the unbalanced min s-t cut problem.

Theoretical Computer Science, 609:658-665, 2016.

PDF:https://www.researchgate.net/publication/353890313_A_New_Approximation_Algorithm_for_the_Unbalanced_Min_s-t_Cut_Problem


[ZCTZ11] Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao.

Approximation and hardness results for Label Cut and related problems.

Journal of Combinatorial Optimization, 21(2):192-208, 2011.

PDF:https://www.researchgate.net/publication/226834589_Approximation_and_hardness_results_for_label_cut_and_related_problems


[LZ13] Angsheng Li, Peng Zhang(*).

Unbalanced graph partitioning.

Theory of Computing Systems, 53(3):454-466, 2013.

(alphabet order)

PDF:https://www.researchgate.net/publication/353860603_Unbalanced_Graph_Partitioning


[ZZL12] Peng Zhang, Daming Zhu, Junfeng Luan.

An approximation algorithm for the generalized k-multicut problem.

Discrete Applied Mathematics, 160(7-8):1240-1247, 2012.

PDF:https://www.researchgate.net/publication/256441907_An_approximation_algorithm_for_the_generalized_k-multicut_problem


[Zha07] Peng Zhang.

A new approximation algorithm for the k-facility location problem.

Theoretical Computer Science, 384(1):126-135, 2007.

PDF:https://www.researchgate.net/publication/353862213_A_New_Approximation_Algorithm_for_the_k-Facility_Location_Problem


*** 学习、工作经历 ***

2021年9月-至今,山东大学软件学院,教授。

2008年5月-2021年8月,山东大学软件学院,讲师,副教授。

2008年5月-2017年12月,山东大学计算机学院,讲师,副教授。

--------------------------------------------------

2013年3月-2014年3月,美国加州大学河滨分校,计算机科学与工程系,访问学者。

2010年1月-2010年6月,微软亚洲研究院,计算理论组,访问学者。

2009年2月-2009年2月,香港大学,计算机系,访问学者。

2008年7月-2008年8月,日本东京工业大学,信息研究科,访问学者。

--------------------------------------------------

2004年9月-2007年7月,中科院软件所,计算机软件与理论,博士学位。

2001年9月-2004年7月,山东大学计算机学院,计算机应用技术,硕士学位。

1996年9月-1999年7月,山东大学计算机系,计算机及其应用,学士学位。


*** 个人主页 & 兴趣爱好 ***

ResearchGate个人主页:https://www.researchgate.net/profile/Peng-Zhang-155

科学网博客:http://blog.sciencenet.cn/?482332

永远的古典吉他:http://blog.sina.com.cn/u/3263131137


*** 发表论文列表 ***

--2023--

[ZYZ23] Xueyang Zhang, Binghao Yan, Peng Zhang.
New algorithms for a simple measure of network partitioning.
Theoretical Computer Science, 2023, published online.
https://doi.org/10.1016/j.tcs.2023.11384


[LZ23] Jiangkun Li, Peng Zhang.

New approximation algorithms for the rooted Budgeted Cycle Cover problem. 

Theoretical Computer Science, 940:283-295, 2023.


--2022--

[YCLZ22] 袁森, 陈开奇, 李江坤, 张鹏. 

最小最大圈覆盖问题的精确算法.

中国科学: 信息科学, 52(6):960-970, 2022.


[Z22] Peng Zhang. 

The LP-rounding plus greed approach for partial optimization revisited. 

Frontiers of Computer Science, 16(1): 161402:1-161402:9, 2022.


[ZYZ22] Xueyang Zhao, Binghao Yan, Peng Zhang.

New algorithms for a simple measure of network partitioning.

TAMC 2022:67-78.


--2021--

[ZL21] Peng Zhang, Zhendong Liu. 

Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph. 

Theoretical Computer Science, 849:173-183, 2021.


[LZ21] Jiangkun Li, Peng Zhang.

New Approximation Algorithms for the Rooted Budgeted Cycle Cover Problem. 

COCOA 2021:167-179.


--2020--

[ZT20] Peng Zhang, Linqing Tang. 

Minimum label s-t cut has large integrality gaps. 

Information and Computation, 275:104543:1-104543:15, 2020.


[LXY+20] Min Li, Dachuan Xu, Jun Yue, Dongmei Zhang, Peng Zhang.

The seeding algorithm for k-means problem with penalties. 

Journal of Combinatorial Optimization, 39(1):15-32, 2020.


[CLL+20] Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, Bing Su, Yao Xu, Peng Zhang.

A (1.4 + epsilon)-approximation algorithm for the 2-Max-Duo problem. 

Journal of Combinatorial Optimization, 40(3):806-824, 2020.


[ZL20] Peng Zhang, Zhendong Liu.

Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph. 

AAIM 2020:161-172.


[Z20] Peng Zhang.

Approximating the Weighted Minimum Label s-t Cut Problem.

arXiv:2011.06204,  2020.


--2019--

[ZZZ+19] Shanshan Zhai, Peng Zhang, Daming Zhu, Weitian Tong, Yao Xu, Guohui Lin. 

An approximation algorithm for genome sorting by reversals to recover all adjacencies. 

Journal of Combinatorial Optimization, 37(4):1170-1190, 2019.


[ZXW+19] Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang, Zhenning Zhang. 

Local search approximation algorithms for the sum of squares facility location problems. 

Journal of Global Optimization, 74(4):909-932, 2019.


[XCZG19] Yao Xu, Yong Chen, Peng Zhang, Randy Goebel.

Approximation algorithms for vertex happiness.

Journal of the Operations Research Society of China, 7:429-448, 2019.


--2018--

[ZXJ+18] Peng Zhang, Yao Xu, Tao Jiang, Angsheng Li, Guohui Lin, Eiji Miyano. 

Improved approximation algorithms for the maximum happy vertices and edges problems. 

Algorithmica, 80(5):1412-1438, 2018.


[ZFT18] Peng Zhang, Bin Fu, Linqing Tang. 

Simpler and better approximation algorithms for the unweighted label s-t cut problem. 

Algorithmica, 80(1):398-409, 2018.


[ZWX18] Peng Zhang, Chenchen Wu, Dachuan Xu. 

Approximation and hardness results for the Max k-Uncut problem. 

Theoretical Computer Science, 749:47-58, 2018.


[WXZZ18] Chenchen Wu, Dachuan Xu, Dongmei Zhang, Peng Zhang. 

Approximation algorithms for the robust/soft-capacitated 2-level facility location problems. 

Journal of Global Optimization, 70:207-222, 2018.


[ZXW+18] Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang, Zhenning Zhang. 

A local search approximation algorithm for a squared metric k-facility location problem. 

Journal of Combinatorial Optimization, 35(4):1168-1184, 2018.


[GMZZ18] Cunjing Ge, Feifei Ma, Peng Zhang, Jian Zhang. 

Computing and estimating the volume of the solution space of SMT(LA) constraints. 

Theoretical Computer Science, 743:110-129, 2018.


--2017--

[XCL+17] Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, Peng Zhang. 

A (1.4 + epsilon)-approximation algorithm for the 2-Max-Duo problem. 

ISAAC 2017:66:1-66:12.


[ZXW+17] Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang, Zhenning Zhang. 

A local search approximation algorithm for a squared metric k-facility location problem. 

COCOA 2017:119-124.


--2016--

[ZF16] Peng Zhang, Bin Fu. 

The label cut problem with respect to path length and label frequency. 

Theoretical Computer Science, 648:72-83, 2016.


[Z16] Peng Zhang. 

A new approximation algorithm for the unbalanced min s-t cut problem. 

Theoretical Computer Science, 609:658-665, 2016.


[ZWXZ16] Peng Zhang, Chenchen Wu, Dachuan Xu, Xinghe Zhang. 

Approximation and hardness results for the max k-uncut problem. 

COCOA 2016:49-61.


--2015--

[ZJL15] Peng Zhang, Tao Jiang, Angsheng Li. 

Improved approximation algorithms for the maximum happy vertices and edges problems. 

COCOON 2015:159-170.


[ZL15] Peng Zhang, Angsheng Li. 

Algorithmic aspects of homophyly of networks. 

Theoretical Computer Science, 593:117-131, 2015.


[KLL+15] Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu. 

Improved parameterized and exact algorithms for cut problems on trees. 

Theoretical Computer Science, 607:455-470, 2015.

(alphabet order)


--2014--

[Z14c] Peng Zhang. 

Unbalanced graph cuts with minimum capacity. 

Frontiers of Computer Science, 8(4):676-683, 2014.


[Z14d] Peng Zhang. 

A new approximation algorithm for the Selective Single-Sink Buy-at-bulk problem in network design. 

Journal of Combinatorial Optimization, 27(4):663-678, 2014.


[LZ14] Hong Liu, Peng Zhang (*). 

On the generalized multiway cut in trees problem. 

Journal of Combinatorial Optimization, 27:65-77, 2014.

(alphabet order)


[KLL+14] Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu. 

Algorithms for cut problems on trees. 

COCOA 2014:283-298.

(alphabet order)


[Z14a] Peng Zhang. 

A new approximation algorithm for the unbalanced min s-t cut problem. 

COCOON 2014:346-356.


[Z14b] Peng Zhang. 

Efficient algorithms for the label cut problems. 

TAMC 2014:259-270.


--2013--

[LZ13] Angsheng Li, Peng Zhang (*). 

Unbalanced graph partitioning. 

Theory of Computing System, 53(3):454-466, 2013.

(alphabet order)


[ZZZ13] Peng Zhang, Wenbo Zhao, Daming Zhu. 

Complexity and approximation results forthe min-sum and min-max disjoint paths problems. 

Computing and Informatics, 32(1):23-45, 2013.


--2012--

[ZZL12] Peng Zhang, Daming Zhu, Junfeng Luan. 

An approximation algorithm for the generalized k-multicut problem. 

Discrete Applied Mathematics, 160(7-8):1240-1247, 2012.


[SCG+12] Yuqing Sun, Dickson K.W. Chiu, Bin Gong, Xiangxu Meng, Peng Zhang. 

Scheduling mobile collaborating workforce for multiple urgent events. 

Journal of Network and Computer Applications, 35(1):156-163, 2012.


[LZ12] Hong Liu, Peng Zhang(*). 

On the generalized multiway cut in trees problem. 

COCOA 2012:151-162.

(alphabet order)


[LZZ12] Hong Liu, Peng Zhang, Daming Zhu. 

On editing graphs into 2-club clusters. 

FAW-AAIM 2012:235-246.


[TZ12] Linqing Tang, Peng Zhang. 

Approximating minimum label s-t cut via linear programming. 

LATIN 2012:655-666.

(alphabet order)


--2011--

[Z11a] Peng Zhang. 

Rent-or-buy network design problem and the sample-augment algorithm: a survey. 

International Journal of Software and Informatics, 5(4):607-636, 2011.


[ZCTZ11] Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao. 

Approximation and hardness results for Label Cut and related problems. 

Journal of Combinatorial Optimization, 21(2):192-208, 2011.


[CLL+11] Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Peng Zhang. 

Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors. 

Chicago Journal of Theoretical Computer Science, Article 1, 1-14, 2011.

(alphabet order)


[Z11b] Peng Zhang. 

A new approximation algorithm for theselective single-sink buy-at-ulk problem in network design. 

COCOA 2011:525-536.


--2010--

[LJZ10] Xin Li, Zhiping Jia, Peng Zhang. 

Feedback Control Real-time Scheduling over Data Streams. 

Journal of Computational Information Systems, 6(4):1051-1059, 2010.


[LJZ+10] Xin Li, Zhiping Jia, Peng Zhang, Ruihua Zhang, Haiyang Wang. 

Trust-based on-demand multipath routing in mobile ad hoc networks. 

IET Information Security, 4(4):212-232, 2010.


[LZ10] Angsheng Li, Peng Zhang(*). 

Unbalanced graph partitioning. 

ISAAC 2010:218-229. 

(alphabet order)


[CLL+10] Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Peng Zhang. 

Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors. 

CATS 2010:3-10.

(alphabet order)


--2009--

[ZX09] Peng Zhang, Mingji Xia. 

An approximation algorithm to the k-Steiner Forest problem. 

Theoretical Computer Science, 410(11):1093-1098, 2009.


[ZCTZ09] Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao. 

Approximation and hardness results for Label Cut and related problems. 

TAMC 2009:460-469.


--2008--

[LZZ08] Weilin Li, Peng Zhang(*), Daming Zhu. 

On constrained facility location problems. 

Journal of Computer Science and Technology, 23(5):740-748, 2008.

(alphabet order)


--2007--

[Z07a] Peng Zhang. 

A new approximation algorithm for the k-facility location problem. 

Theoretical Computer Science, 384(1):126-135, 2007.


[XZZ07] Mingji Xia, Peng Zhang, Wenbo Zhao. 

Computational complexity of counting problems on 3-regular planar graphs. 

Theoretical Computer Science, 384:111-125, 2007.


[Z07b] Peng Zhang. 

An approximation algorithm to the k-Steiner Forest problem. 

TAMC 2007:728-737.


[Z07c] Peng Zhang. 

Approximating generalized Multicut on trees. 

CiE 2007:799-808.


[ZZ07a] Wenbo Zhao, Peng Zhang. 

Approximation to the minimum rooted star cover problem. 

TAMC 2007:670-679.


[ZZ07b] Peng Zhang, Wenbo Zhao. 

On the complexity and approximation of the min-sum and min-max disjoint paths problems. 

ESCAPE 2007:70-81.


--2006--

[ZZJ06] Wenbo Zhao, Peng Zhang, Tao Jiang. 

A network flow approach to the Minimum Common Integer Partition Problem. 

Theoretical Computer Science, 369(1-3):456-462, 2006.


[Z06] Peng Zhang. 

A new approximation algorithm for the k-facility location problem. 

TAMC 2006:217-230. 


*** 早期职业生涯 ***

在攻读研究生学位之前,从事过十几个规模项目开发工作,包括基础软件、管理信息系统、单片机应用系统、计算机自动控制系统等。在某医疗设备的控制系统设计中,为了提高硬件系统的可靠性,减少中间环节,摒弃了传统的上位机+下位机开发模式,而是采用PC机独立完成控制任务。为了能够实时、可靠地完成控制动作,没有采用厂商提供的驱动程序,而是面向PCI数据采集板卡编写了设备驱动程序(VxD设备驱动程序(Win95)、WDM设备驱动程序(WinXP/7)),在操作系统核心层通过中断方式直接操纵板卡,实现了PC机对医疗设备的直接控制。该系统稳定可靠,获得了长期广泛的批量应用。项目开发中使用的技术,总结成论文《基于PCI总线数据采集卡的实时测控技术》,发表在2009年的《生物医学工程研究》期刊上。


*** 名人名言 ***

“就像格罗滕迪克所说,“构成一个研究者创造力和想象力的本质,是他们聆听事情内部声音的能力。”这里没有等级高下,没有阶层之分,在对未知的探索前人人平等,每个人都拥有绝对的自由。”——许晨阳。

研究概况

理论计算机科学包含许多内容,算法和计算理论是其中一个重要的组成部分。给定一个计算模型(电子计算机是计算模型的一个具体例子),该模型能够解决什么样的问题?能够解决多难的问题?这多半是出于人们的好奇心。给定一个问题,如何设计算法解决该问题?算法求解的性能如何评价?解决该问题至少需要什么样的计算模型?这多半是人们觉得这样的问题“有用”。新的时代涌现新的科学问题,新的科学问题呼唤新的算法求解。因此,算法是一棵常青树。古往今来,知识就是在“有趣”和“有用”的双重推动下,不断创新,不断向前发展。


研究方向:算法设计与分析,组合最优化,计算复杂性。
应用领域:网络算法和大数据算法。

论文

(1) 赵雪旸.New algorithms for a simple measure of network partitioning.Theoretical Computer Science.2023,957

(2) 李江坤.New approximation algorithms for the rooted Budgeted Cycle Cover problem.Theoretical Computer Science.2023,940 :283

(3) 张鹏.The label cut problem with respect to path length and label frequency.Theoretical Computer Science.2016,648 :72-83

(4) 张鹏.Algorithmic aspects of homophyly of networks.Theoretical Computer Science.2015,593 :117-131

(5) 郝凡昌.通过交互式移位-插入-删除进行基因组排序的较快算法.《计算机研究与发展》.2010,47 (11):2011-2023

(6) 张鹏.Unbalanced graph cuts with minimum capacity.Frontiers of Computer Science.2014,8 (4):676-683

(7) A (1.4+epsilon)-approximation algorithm for the 2-MAX-DUO problem.JournalofCombinatorialOptimization.2020,40 (3):806

(8) 李江坤.New approximation algorithms for the rooted Budgeted Cycle Cover problem.Theoretical Computer Science.2023 (940)

(9) 赵雪旸.New algorithms for a simple measure of network partitioning.Theoretical Computer Science.2023 (957)

(10) 张鹏.An approximation algorithm for the Generalized k-Multicut problem.Discrete Applied Mathematics.2012,160 (7-8):1240-1247

(11) 张鹏.The LP-rounding plus greed approach for partial optimization revisited.Frontiers of Computer Science.2022,16 (1)

(12) 栾峻峰.通过交互式移位,插入,删除进行基因组排序的较快算法.《计算机研究与发展》.2010,47 (11):2011

(13) 张鹏.The LP-rounding plus greed approach for partial optimization revisited.Frontiers of Computer Science.2022,16 (1)

(14) Li, Min.The seeding algorithm for k-means problem with penalties.JournalofCombinatorialOptimization.2020,39 (1):15

(15) 张鹏.Minimum Label s-t Cut has large integrality gaps.INFORMATION AND COMPUTATION.2020,275 (275)

(16) 张鹏.Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph.2020

(17) 张鹏.Unbalanced Graph Partitioning.Theory of Computing Systems.2013,53 (3):454

(18) Chen, Yong.A (1.4+epsilon)-approximation algorithm for the 2-MAX-DUO problem.JournalofCombinatorialOptimization.2020,40 (3):806

(19) 张鹏.Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph.Theoretical Computer Science.2021,849 :173

(20) 张鹏.Minimum label s-t cut has large integrality gaps.INFORMATION AND COMPUTATION.2020 (1)

(21) 翟姗姗.An approximation algorithm for genome sorting by reversals to recover all adjacencies.JournalofCombinatorialOptimization.2019,37 (4):1170

(22) 张鹏.On the generalized multiway cut in trees problem.Journal of Combinatorial Optimization.2014,27 :65

(23) 孙宇清.Scheduling Mobile Collaborating Workforce for Multiple Urgent Events.Journal of Network and Computer Applications.2012,35 (1):156

(24) 张鹏.Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems.Algorithmica.2018,80 (5):1412

(25) 张鹏.Approximation and hardness results for the max k-uncut problem.Theoretical Computer Science.2018,749 (1):47

(26) 张鹏.Simpler and better approximation algorithms for the unweighted label s-t cut problem.Algorithmica.2018,80 (1):398

(27) 张鹏.Complexity and approximation results for the min-sum and min-max disjoint paths problems.Computing and Informatics.2013,32 (1):23

(28) 张鹏.Approximating minimum label s-t cut via linear programming.Lecture Notes in Computer Science / LATIN 2012.2012

(29) 孙宇清.Scheduling Mobile Collaborating Workforce for Multiple Urgent Events.Journal of Network and Computer Applications.2012,35 (1):156

(30) 李新.Feedback Control Real-time Scheduling over Data Streams.《Journal of Computational Information Systems》.2010,6 (4):1051

(31) 张鹏.Approximation and hardness results for the max k-uncut problem.Lecture notes in computer science / COCOA 2016.2016

(32) 张鹏.The label cut problem with respect to path length and label frequency.Theoretical Computer Science.2016,648 :72

(33) 张鹏.Improved approximation algorithms for the maximum happy vertices and edges problems.Lecture Notes in Computer Science.2015,9198 :159

(34) 张鹏.Algorithmic aspects of homophyly of networks.Theoretical Computer Science.2015,593 :117

(35) 张鹏.A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design.Journal of Combinatorial Optimization.2014,27 (4):663

(36) 张鹏.Unbalanced graph cuts with minimum capacity.Fronties of Computer Science.2014,8 (3):676

(37) 张鹏.A bicriteria approximation algorithm for generalized k-multicut in trees.IEEE CSO 2009.2009 :699

(38) 张鹏.Unbalanced graph partitioning.Lecture Notes in Computer Science / ISAAC 2010.2010

(39) 张鹏.A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design.Lecture Notes in Computer Science / COCOA 2011.2011

(40) 张鹏.An approximation algorithm to the k-Steiner Forest problem.Theoretical Computer Science.2009,410 (11):1093

(41) 张鹏.Approximation and hardness results for Label Cut and related problems.Journal of Combinatorial Optimization.2011,21 (2):192

(42) 张鹏.On the generalized multiway cut in trees problem.Journal of Combinatorial Optimization.2014,27 :65

(43) 张鹏.An approximation algorithm for the generalized k-multicut problem.Discrete Applied Mathematics.2012,160 (7-8):1240

(44) 张鹏.Efficient algorithms for the label cut problem.lecture notes in computer science / TAMC 2014.2014

(45) 张鹏.On the generalized multiway cut in trees problem.Lecture Notes in Computer Science / COCOA 2012.2012,1 (1):151

(46) 李新.A Trust-based Multipath Routing Framework for Mobile Ad Hoc Networks.2010 7th International Conference on Fuzzy Systems and Knowledge Discovery,FSKD 2010.2010,1 (1):773

(47) 李新.Trust-based On-demand Multipath Routing in Mobile Ad Hoc Networks.IET Information Security.2010,4 (4):212

(48) 张鹏.Unbalanced Graph Partitioning(CCF-C).Theory of Computing Systems.2013,53 (3):454

(49) 张鹏.A new approximation algorithm for the unbalanced min s-t cut problem.Theoretical Computer Science.2016

(50) 孙宇清.Scheduling Mobile Collaborating Workforce for Multiple Urgent Events.Journal of Network and Computer Applications.2012,35 (1):156

(51) 李新.Feedback Control Real-time Scheduling over Data Streams.《Journal of Computational Information Systems》.2010,6 (4):1051

(52) 李新.A Trust-based Multipath Routing Framework for Mobile Ad Hoc Networks.2010 7th International Conference on Fuzzy Systems and Knowledge Discovery,FSKD 2010.2010,1 (1):773

(53) 李新.Trust-based On-demand Multipath Routing in Mobile Ad Hoc Networks.IET Information Security.2010,4 (4):212

(54) 孙宇清.Scheduling Mobile Collaborating Workforce for Multiple Urgent Events.Journal of Network and Computer Applications.2012,35 (1):156

(55) 李新.A Trust-based Multipath Routing Framework for Mobile Ad Hoc Networks.2010 7th International Conference on Fuzzy Systems and Knowledge Discovery,FSKD 2010.2010,1 (1):773

(56) 李新.Feedback Control Real-time Scheduling over Data Streams.《Journal of Computational Information Systems》.2010,6 (4):1051

(57) 李新.Trust-based On-demand Multipath Routing in Mobile Ad Hoc Networks.IET Information Security.2010,4 (4):212

(58) 张鹏.Approximation and hardness results for the max k-uncut problem.Lecture notes in computer science / COCOA 2016.2016

(59) 张鹏.The label cut problem with respect to path length and label frequency.Theoretical Computer Science.2016,648 :72

(60) 张鹏.A new approximation algorithm for the unbalanced min s-t cut problem .Theoretical Computer Science.2016

(61) 张鹏.Improved approximation algorithms for the maximum happy vertices and edges problems.Lecture Notes in Computer Science.2015,9198 :159

(62) 张鹏.Algorithmic aspects of homophyly of networks.Theoretical Computer Science.2015,593 :117

(63) 张鹏.Efficient algorithms for the label cut problem.lecture notes in computer science / TAMC 2014.2014

(64) 张鹏.On the generalized multiway cut in trees problem.Journal of Combinatorial Optimization.2014,27 :65

(65) 张鹏.A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design.Journal of Combinatorial Optimization.2014,27 (4):663

(66) 张鹏.Unbalanced graph cuts with minimum capacity.Fronties of Computer Science.2014,8 (3):676

(67) 张鹏.Complexity and approximation results for the min-sum and min-max disjoint paths problems.Computing and Informatics.2013,32 (1):23

(68) 张鹏.Unbalanced Graph Partitioning.Theory of Computing Systems.2013,53 (3):454

(69) 张鹏.A bicriteria approximation algorithm for generalized k-multicut in trees.IEEE CSO 2009.2009 :699

(70) 张鹏.Unbalanced graph partitioning.Lecture Notes in Computer Science / ISAAC 2010.2010

(71) 张鹏.An approximation algorithm to the k-Steiner Forest problem.Theoretical Computer Science.2009,410 (11):1093

(72) 张鹏.Approximation and hardness results for Label Cut and related problems.Journal of Combinatorial Optimization.2011,21 (2):192

(73) 张鹏.Approximating minimum label s-t cut via linear programming.Lecture Notes in Computer Science / LATIN 2012.2012

(74) 张鹏.An approximation algorithm for the generalized k-multicut problem.Discrete Applied Mathematics.2012,160 (7-8):1240

(75) 张鹏.Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems.Algorithmica.2018

版权所有   ©山东大学 地址:中国山东省济南市山大南路27号 邮编:250100 
查号台:(86)-0531-88395114
值班电话:(86)-0531-88364731 建设维护:山东大学信息化工作办公室