2. 您的位置
3. 首页
4. 期刊论文
5. A class of polynomially solvable 0-1 programming problems and an application

A class of polynomially solvable 0-1 programming problems and an application

来源 :中国科学：数学英文版 | 被引量 : 0次 | 上传用户：billysjq

【摘 要】

：

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP.

【作 者】

：

Wang Miao Xie JinXing Xiong Hu 

【机 构】

：

TsinghuaUniv

【出 处】

：

中国科学：数学英文版

【发表日期】

：

2011年3期

【关键词】

：

0-1规划问题 多项式可解 应用程序 多项式时间算法 供应链管理 NP完全 工业应用 最佳解 0-1 programming polynomial-time a 

【基金项目】

：

supported by National Natural Science Foundation of China （Grant Nos.70471008 70971072）

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially so

其他文献

Heteroclinic orbits and heteroclinic chains for a discrete Hamiltonian system

In the present work we prove some existence results of heteroclinic orbits and heteroclinic chains for a second order discrete Hamiltonian system of the form Δ

期刊

DIFFERENCEequationHETEROCLINICORBITHETEROCLINICCHAINVARIATIONALmethoddif

On periodic groups with prescribed orders of elements

This is a survey of results and open problems concerning the structure of periodic group with prescribed orders of their elements. In particular, an outline of

期刊

SPECTRUMPERIODICGROUPlocalFINITENESSspectrum periodic group local finitenes

Interpolation theory of anisotropic finite elements and applications

Interpolation theory is the foundation of finite element methods.In this paper,after reviewing some existed interpolation theorems of anisotropic finite element

期刊

INTERPOLATIONtheoryANISOTROPICFINITEELEMENTSNewton’sFORMULAdividedDIFFER

Gorenstein flatness and injectivity over Gorenstein rings

Let R be a Gorenstein ring.We prove that if I is an ideal of R such that R/I is a semi-simple ring,then the Gorenstein flat dimension of R/I as a right R-module

期刊

GORENSTEINFLATGORENSTEININJECTIVEGORENSTEINRINGSGorenstein flat Gorenstein

The genus polynomials of cross-ladder digraphs in orientable surfaces

Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by

期刊

GRAPHGENUSdistributionGENUSSURFACESgraph genus distribution genus surfaces

Essential normality of linear fractional composition operators in the unit ball of C~N

Let φ be a linear fractional self-map of the ball BN with a boundary fixed point e1,we show that1φReφ1(z)～Re(1-z1)holds in a neighborhood of e1 on BN.Applying

期刊

compositionOPERATORSessentialNORMALITYHARDYspaceBERGMANSPACEScomposition

On the rate of convergence of the maximum likelihood estimator of a k-monotone density

Bounds for the bracketing entropy of the classes of bounded k-monotone functions on [0,A] are obtained under both the Hellinger distance and the Lp(Q) distance,

期刊

bracketingmetricENTROPYMAXIMUMLIKELIHOODESTIMATORHellingerDISTANCEbracke

Infinitely many radial solutions to elliptic prob-lems with critical Sobolev and Hardy terms

Let Ω RN be a ball centered at the origin with radius R 】 0 and N 7, 2* = 2N/N-2. We obtain the existence of infinitely many radial solutions for the Dirich

期刊

NODALsolutionsCOMPACTNESScriticalSOBOLEVandHARDYTERMSnodal solutions com

Near generalized balanced tournament designs with block sizes 4 and 5

A near generalized balanced tournament design, or an NGBTD(k,m) in short, is a (km+1,k,k-1)-BIBD defined on a (km+1)-set V . Its blocks can be arranged into an

期刊

nearGENERALIZEDBALANCEDTOURNAMENTDESIGNSframeGENERALIZEDdoublyRESOLVABLE

Brake subharmonic solutions of first order Hamiltonian systems

In this paper,we mainly use the Galerkin approximation method and the iteration inequalities of the L-Maslov type index theory to study the properties of brake

期刊

BRAKESUBHARMONICSOLUTIONL-MaslovtypeINDEXHAMILTONIANsystemsbrake subharm