张鹏 副教授 个人空间

张鹏   副教授

山东大学软件学院
人工智能研究所智能算法实验室

办公室:教师楼323室
电子邮件:algzhang@sdu.edu.cn
科学网个人主页:http://blog.sciencenet.cn/?482332
DBLP论文列表:http://dblp.uni-trier.de/pers/hd/z/Zhang_0008:Peng
ResearchGate个人主页:https://www.researchgate.net/profile/Peng_Zhang48
永远的古典吉他:http://algzhang.blog.163.com



2018年1月-至今,山东大学软件学院,副教授
2017年,山东大学计算机学院东迁青岛校区
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月,山东大学计算机系,计算机及其应用,学士学位。

招生意向


从事算法和计算理论研究,以及相关软件设计与研发。可招收“计算机科学与技术”和“软件工程”两个专业的研究生。

研究方向


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

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

讲授课程


本科生课程:算法设计与分析,运筹学,线性代数,概率与统计
研究生课程:高级算法设计,可计算性与计算复杂性

承担项目


(7)主持,国家自然科学基金面上项目,《网络同质性原理和图划分问题的近似算法》,2017-2020,在研。
(6)主持,山东省自然科学基金面上项目,《面向现代应用的网络最小割问题的近似算法与近似困难性研究》,2016-2019,在研。
(5)主持,山东大学自主创新基金项目,《网络割集问题的近似算法及其应用》,2012-2014,已结题。
(4)主持,国家自然科学基金面上项目,《网络链路选择问题的近似算法》,2010-2012,已结题。
(3)主持,山东省博士后创新基金一等资助项目,《网络设计问题的近似算法设计与分析》,2009,已结题。
(2)主持,国家博士后基金特别资助项目,《多重割集问题的近似算法》,2009,已结题。
(1)主持,国家博士后基金面上项目,《网络割集问题的近似算法与近似难度》,2008,已结题。

发表论文


(·)共发表期刊论文和会议论文40余篇,其中以第一作者和通讯作者发表SCI索引期刊论文18篇。论文主要发表在算法和计算理论领域的主流国际期刊Algorithmica,ToCS,TCS,JGO,DAM等,以及主流国际会议LATIN,ISAAC,COCOON等上。
(·)在DBLP上的发表论文列表,请参阅:http://dblp.uni-trier.de/pers/hd/z/Zhang_0008:Peng

---------------------------------------
研究工作1:设施选址问题
(·)使用局部搜索的方法,对经典的k-设施位置问题(k-Facility Location)给出了近似比为3.7321的近似算法,这也是关于该问题目前已知最好近似比。相关论文[Zha07]被组合优化领域的流行专著《Combinatorial Optimization: Theory and Algorithms》(Korte, Vygen著,Springer出版社,第5版,2012)引用。
(·)根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[Zha07a, TCS]已被引用50次。

---------------------------------------
研究工作2:标签s-t割问题
(·)标签s-t割问题是来自系统安全、计算机网络等领域的一个优化问题,是经典的最小s-t割问题的推广。给一个图,边上有标签,该问题询问最小数目的标签,使得在图上去掉具有这些标签的边之后,能够断开给定的(s, t)顶点对。
(·)论文[ZCTZ11, JOCO]使用贪心的技术,对该问题给出了近似比为m^{1/2}的近似算法。根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[ZCTZ11, JOCO]已被引用25次。
(·)论文[TZ12, LATIN]使用线性规划舍入的技术,对该问题给出了近似比为m^{1/2} / OPT^{1/2}的近似算法和近似比为n^{2/3} / OPT^{1/3}的近似算法。
(·)论文[ZFT16, ALGO]使用纯组合的技术,对该问题给出了近似比为m^{1/2} / OPT^{1/2}的近似算法和近似比为n^{2/3} / OPT^{1/3}的近似算法。

---------------------------------------
研究工作3:非平衡割问题
(·)非平衡最小s-t割问题询问s一侧顶点数目不超过k的最小s-t割。论文[LZ10, ISAAC]对该问题给出了近似比为O(log n)的近似算法,论文[Zha16, TCS]对该问题给出了近似比为O(k)的近似算法。
(·)非平衡最稀疏割(Sparsest Cut)问题询问一侧顶点数目不超过k的稀疏度最小的割。非平衡最小传导率(Min Conductance)问题询问一侧顶点数目不超过k的传导率最小的割。这两个问题来自于对社会网络的研究。论文[LZ13, ToCS]对这两个问题给出了首个双准则近似算法。
(·)根据谷歌学术和百度学术的统计,截至2015年12月5日,论文[LZ13, ToCS]已被引用11次。

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

---------------------------------------
研究工作5:网络同质性相关问题的研究
(·)提出并研究了最大满意边问题和最大满意顶点问题。一条边,若其两个端点具有相同的颜色,则该边称为满意的。一个顶点,若其所有邻接边都是满意的,则该顶点称为满意的。给一个图,部分顶点已经着色,最大满意边问题寻找一种着色方案,使满意边的数目最多。类似地,最大满意顶点问题寻找一种着色方案,使满意顶点的数目最多。
(·)论文[ZXJ+17, ALGO]使用线性规划随机舍入技术,对这两个问题分别给出了近似比为0.8535和1/Delta的近似算法。

---------------------------------------
[ZWX17] Peng Zhang, Chenchen Wu, Dachuan Xu. Approximation and hardness results for the max k-uncut problem. TCS, published online, 2017+

--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.
[WXZZ18] Chenchen Wu, Dachuan Xu, Dongmei Zhang, Peng Zhang. Approximation algorithms for the robust/soft-capacitated 2-level facility location problems. JGO, 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. JOCO, 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. TCS, 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. TCS, 648:72-83, 2016.
[Zha16] Peng Zhang. A new approximation algorithm for the unbalanced min s-t cut problem. TCS, 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. TCS, 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. TCS, 607:455-470, 2015.(alphabet order)

--2014--
[Zha14] Peng Zhang. Unbalanced graph cuts with minimum capacity. FCS, 8(4):676-683, 2014.
[Zha14] Peng Zhang. A new approximation algorithm for the Selective Single-Sink Buy-at-bulk problem in network design. JOCO, 27(4):663-678, 2014.
[LZ14] Hong Liu, Peng Zhang(*). On the generalized multiway cut in trees problem. JOCO, 27:65-77, 2014.
[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)
[Zha14a] Peng Zhang. A new approximation algorithm for the unbalanced min s-t cut problem. COCOON 2014:346-356.
[Zha14b] Peng Zhang. Efficient algorithms for the label cut problems. TAMC 2014:259-270.

--2013--
[LZ13] Angsheng Li, Peng Zhang(*). Unbalanced graph partitioning. ToCS, 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. CAI, 32(1):23-45, 2013.

--2012--
[ZZL12] Peng Zhang, Daming Zhu, Junfeng Luan. An approximation algorithm for the generalized k-multicut problem. DAM, 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.

--2011--
[Zha11a] 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. JOCO, 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)
[Zha11b] 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. TCS, 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. JCST, 23(5):740-748, 2008.(alphabet order)

--2007--
[Zha07a] Peng Zhang. A new approximation algorithm for the k-facility location problem. TCS, 384(1):126-135, 2007.
[XZZ07] Mingji Xia, Peng Zhang, Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. TCS, 384:111-125, 2007.
[Zha07b] Peng Zhang. An approximation algorithm to the k-Steiner Forest problem. TAMC 2007:728-737.
[Zha07c] 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. TCS, 369(1-3):456-462, 2006.
[Zha06] Peng Zhang. A new approximation algorithm for the k-facility location problem. TAMC 2006:217-230.

本人研究生从事的工作领域


高强,高校。
金有伟,河北广电网络集团。
刘喜荣,高校。
周阿柳,高校。
颜庆,国家电网山东电力科学研究院。