位置：立项数据库 > 立项详情页
NP困难排序问题的可近似性
  • 项目名称：NP困难排序问题的可近似性
  • 项目类别：青年科学基金项目
  • 批准号：10101007
  • 申请代码：A011202
  • 项目来源：国家自然科学基金
  • 研究期限：2002-01-01-2004-12-01
  • 项目负责人：刘朝晖
  • 负责人职称：教授
  • 依托单位：华东理工大学
  • 批准年度：2001
中文摘要：

本课题是一项跨应用数学、理论计算机科学和运筹学的交叉项目。主要目的是利用一些最近几年发展起来的新方法研究NP困难排序问题的可近似性，特别是关于"求和形式"排序问题，希望能获得好的近似算法和不可近似性结果，解决排序理论研究前沿的一些待解决问题。本课题的完成对排序、甚至是组合最优化与计算复杂性理论的发展有较大意义。

中文主题词： 排序；NP困难性；可近似性
结论摘要：

英文主题词scheduling;NP-hardness;approximability

成果综合统计
成果类型
数量
  • 期刊论文
  • 会议论文
  • 专利
  • 获奖
  • 著作
  • 13
  • 0
  • 0
  • 0
  • 0
期刊论文
Minimizing total completion time subject to job release dates and preemption penalties
Parallel machine scheduling to minimize the sum of quadratic completion times
The unbounded single machine parallel batch scheduling problem with family jobs and release dates to
Approximation schemes for minimizing total (weighted) completion time with release dates on a batch
3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints
Approximability of two-machine no-wait flowshop scheduling with availability constraints
关于延误时间的平行机排序问题的复杂性
相关项目
基于反馈式排序框架F-Rank的查询导向的更新式多文档自动摘要研究
期刊论文 7 会议论文 10 专利 2
排序若干新问题的算法设计与分析
期刊论文 19 会议论文 3
若干在线排序问题高性能算法及其应用研究
期刊论文 13 会议论文 4
维、哈、柯多文种信息检索技术研究
期刊论文 3
基于用户选择与判断的Web信息搜索技术研究
期刊论文 9 会议论文 7
网络排序问题的高性能优化算法研究
期刊论文 15 会议论文 2
流水作业排序问题的在线算法设计与竞争比分析
期刊论文 2 会议论文 2
多阶段集成排序和退化机器环境下排序的理论研究
期刊论文 17 会议论文 1
若干新型排序问题研究
期刊论文 12 会议论文 1
刘朝晖的项目
网络排序问题的高性能优化算法研究
期刊论文 15 会议论文 2
排序和路线问题复杂性和在线算法
期刊论文 16
一些路线和调度问题的算法与理论研究