Computing an integer point of a class of convex sets

被引:0
作者
Dang, C [1 ]
机构
[1] City Univ Hong Kong, Dept Mfg Engn & Engn Management, Hong Kong, Hong Kong, Peoples R China
关键词
integer points; integer labeling; triangulations; simplicial methods;
D O I
10.1023/A:1026438301292
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
A simplicial algorithm is proposed for computing an integer point of a convex set C subset of R-n satisfying chi = max {chi (1), chi (2)} = (max {chi (1)(1), chi (2)(1)}, ... , max {chi (1)(n),chi (2)(n)})(T) is an element of C, with chi (1) = (chi (1)(1), chi (1)(2), ... , chi (1)(n))(T) is an element of C, chi (2) = (chi (2)(1), chi (2)(2), ... , chi (2)(n))(T) is an element of C. The algorithm subdivides R-n into integer simplices and assigns an integer label to each integer point of R-n. Starting at an arbitrary integer point, the algorithm follows a finite simplicial path that leads either to an integer point of C or to the conclusion that C has no integer point.
引用
收藏
页码:333 / 348
页数:16
相关论文
共 21 条
[1]   SIMPLICIAL AND CONTINUATION METHODS FOR APPROXIMATING FIXED-POINTS AND SOLUTIONS TO SYSTEMS OF EQUATIONS [J].
ALLGOWER, E ;
GEORG, K .
SIAM REVIEW, 1980, 22 (01) :28-85
[2]  
[Anonymous], 1973, The Computation of Economic Equilibria
[3]  
DANG C, IN PRESS J COMPUTATI
[4]   A simplicial approach to the determination of an integer point of a simplex [J].
Dang, CY ;
Van Maaren, H .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (02) :403-415
[6]   An arbitrary starting variable dimension algorithm for computing an integer point of a simplex [J].
Dang, CY ;
Van Maaren, H .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1999, 14 (01) :133-155
[7]  
Eaves BC, 1972, Math. Programming, V3, P1, DOI 10.1007/BF01584975
[8]  
EAVES BC, 1972, MATHEMATICAL PROGRAM, V3, P225
[9]  
Forster W., 1995, HDB GLOBAL OPTIMIZAT, P669
[10]   Simplicial analyses of a restricted flatness [J].
Freudenthal, H .
ANNALS OF MATHEMATICS, 1942, 43 :580-582