单机排序问题1Pk≥Pq→Pk/Wp〉Pq/Wqn∑q=1WqCq—dq近似…

来源 :武汉冶金科技大学学报 | 被引量 : 0次 | 上传用户:gorgeous1277
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Lawler和Lenstra已证明:单机排序问题1‖n∑q=1Wqmax(cq-dq),0)是“强”NP完全的,而该问题是1‖n∑q=1Wqcq-dq的子问题,因而也是强NP完全问题,没有好算法,本文在假设Pk≥Pq→Pk/Wk〉Pq/Wq成立的条件下,设计出求该问题的近似最优解的伪多项式时间算法。
其他文献
景泰四中前身是甘肃省水利水电工程局职工子弟学校,始建于1970年10月,1999年3月移交景泰县管理。学校秉承“依靠科技,敢为人先,艰苦创业,造福于民”的景电精神,现已发展成为景泰县
冶金起重机主梁的疲劳破坏通常发生在上盖板主焊缝和下盖板对接焊缝处。本文分析了主焊缝的应力状态和引起疲劳破坏的主要因素,介绍了疲劳强度校核和步骤。以金属结构工作级别
通过对液压挖掘机在工作过程中工作装置所受到的力和运动之间关系的研究,对液压系统液体流动和工作装置运动分别对挖掘力的影响作出了定量分析,并建立了相应的数学模型。关键在
本文讨论了B值正鞅的诱导集函烽的Lebesgue分解和此集函数绝对连续性的充要条件。
恶性肿瘤骨转移临床表现为疼痛、高钙血症及病理性骨折,严重影响患者生存质量。2005年7月~2006年12月。我们应用唑来膦酸治疗恶性肿瘤骨转移58例,疗效满意。现报告如下。
本文参照了斜刃剪剪切力的计算方法,推导出了适合滚切剪剪切力的计算公式,并用实验数据进行了验证。
在精准扶贫的攻坚决胜阶段,做好文化扶贫是转变人民思想观念,扩大精准帮扶效果,防止脱贫群众返贫的关键举措。在分析文化扶贫的内涵、作用及面临问题的基础上,结合张家口市的
以Web技术为基础,利用Internet/Intranet技术设计和研制开发了查询多种平台档案信息的管理系统,可支持多种软、硬件平台(多种机型和操作系统),具有统一的用户界面,统一的语言格式,统一的传输协议。它既能
韩国高等教育高校采取政府、社会和学校相互渗透、互为制约、互为纾解的人事管理机制,既达到依法依规管理人事的目的,也最大限度地保障了教师的合法权益。中国高校应借鉴韩国
超语言信息泛指话语和文字背后的信息,包括语境,背景知识,文化因素,比喻含义,信息形式,语题主题,原文类别,俚语行话,等等,超语言涉及到语用学,语义学,词汇学,修刮学,社会学,心理学,文学,历史等