Solving Linear Programming with Constraints Unknown
作者： Xiaohui Bei , Ning Chen , Shengyu Zhang
DOI: 10.1007/978-3-662-47672-7_11
关键词:
摘要: What is the value of input information in solving linear programming? The celebrated ellipsoid algorithm tells us that full constraints not necessary; works as long there exists an oracle that, on a proposed candidate solution, returns violation form separating hyperplane. Can programming still be efficiently solved if returned other formats?
springer.com
mpg.de
core.ac.uk
arxiv.org
sci-hub.se 参考文章(26)
M. Grötschel, L. Lovász, A. Schrijver, Geometric Methods in Combinatorial Optimization Progress in Combinatorial Optimization (W.R. Pulleyblank, ed.). pp. 167- 183 ,(1984) , 10.1016/B978-0-12-566780-7.50016-7
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram, On the Complexity of Trial and Error for Constraint Satisfaction Problems international colloquium on automata, languages and programming. ,vol. 92, pp. 48- 64 ,(2018) , 10.1016/J.JCSS.2017.07.005
Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small Journal of the ACM. ,vol. 42, pp. 488- 499 ,(1995) , 10.1145/201019.201036
Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed Journal of the ACM. ,vol. 31, pp. 114- 127 ,(1984) , 10.1145/2422.322418
M. D. Kovalev, A property of convex sets and its application Mathematical Notes. ,vol. 44, pp. 537- 543 ,(1988) , 10.1007/BF01158120
David Hartvigsen, Recognizing Voronoi Diagrams with Linear Programming Informs Journal on Computing. ,vol. 4, pp. 369- 374 ,(1992) , 10.1287/IJOC.4.4.369
Gil Kalai, A subexponential randomized simplex algorithm (extended abstract) symposium on the theory of computing. pp. 475- 482 ,(1992) , 10.1145/129712.129759
Christos H. Papadimitriou, Mihalis Yannakakis, Linear programming without the matrix Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 121- 129 ,(1993) , 10.1145/167088.167127
L.G. Khachiyan, Polynomial algorithms in linear programming USSR Computational Mathematics and Mathematical Physics. ,vol. 20, pp. 53- 72 ,(1980) , 10.1016/0041-5553(80)90061-0
M. E. Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem SIAM Journal on Computing. ,vol. 15, pp. 725- 738 ,(1986) , 10.1137/0215052