| Properly Weighted Independence Systemsand Applications to Scheduling Problems |
| |
| 引用本文： | YIXUN LIN JUNQIANG DENG(Department of Mathematics,Zhengzhou University,Zhengzhou,Henan 450052). Properly Weighted Independence Systemsand Applications to Scheduling Problems[J]. 运筹学学报, 1997, 0(2) |
| |
| 作者姓名： | YIXUN LIN JUNQIANG DENG(Department of Mathematics Zhengzhou University Zhengzhou Henan 450052) |
| |
| 作者单位： | Department of Mathematics，Zhengzhou University，Zhengzhou，Henan 450052 |
| |
| 摘 要： | 1.IntroductionIncombinatorialoptimizationthetheoryofindependencesystemsplaysanimportantrole.Oneofthereasonswasthatawiderangeofpracticalproblemscanbeformulatedasthemaximumweightindependentsetproblem(MWIprobleminshort)onanindependencesystem.AmatroidisaspecialindependencesystemwiththecharacterizationthatthegreedyalgorithmcanalwaysworkforthecorrespondingMWIproblemwithanyweightfunction.Thisisafundamentalgreedilysolvablecase11,21.Theothergreedilysolvablecaseshavereceivedstronginterestsinrecentyea…
|
Properly Weighted Independence Systems and Applications to Scheduling Problems |
| |
| YIXUN LIN JUNQIANG DENG. Properly Weighted Independence Systems and Applications to Scheduling Problems[J]. OR Transactions, 1997, 0(2) |
| |
| Authors: | YIXUN LIN JUNQIANG DENG |
| |
| Abstract: | The theory of independence systems is powerful in combinatorial optimization. Itis well-known that the greedy algorithm solves the maximum weight independent setproblem for a matroid with any weight function. However, this may not be true fora general independence system. In this paper we propose a condition on the weightfunctions (called the proper weight functions) that guarantees the greedy solvability foran independence system. Applying this general result to scheduling problems, some newinsights, as well as new algorithms, are obtained. |
| |
| Keywords: | Combinatorial optimization Independence system Greedy algorithm Scheduling |
| 本文献已被 CNKI 等数据库收录！ |
