On the Number of Irreducible Points in Polyhedra

1. Alekseyev, M.A., Basova, M., Zolotykh, N.Yu.: On the minimal teaching sets of two-dimensional threshold functions. SIAM J. Discrete Math. 29(1), 157–165 (2015)

2. Antony, M., Brightwell, G., Shawe-Taylor, J.: On exact specification by labelled examples. Discrete Appl. Math. 61(1), 1–25 (1995)

   Article  MathSciNet  MATH  Google Scholar 

3. Angluin, D.: Queries and concept learning. Discrete Appl. Math. 2, 319–342 (1988)

   MathSciNet  Google Scholar 

4. Bárány, I., Howe, R., Lovász, L.: On integer points in polyhedra: a lower bound. Combinatorica 12(2), 135–142 (1992)

   Article  MathSciNet  MATH  Google Scholar 

5. Chirkov, A.Yu.: Caratheodory’s theorem and coverings of a polyhedron by simplexes. Manuscript No. 668B93, deposited at VINITI, Moscow, (1993). (in Russian)

6. Chirkov, A.Yu.: On the lower bound for the number of vertices of convex hull of integer and partially integer points of a polyhedron. Discrete Anal. Oper. Res. 3(2), 80–89 (1996)

7. Chirkov, A.Yu.: The relationship between upper bounds of the number of vertices of convex hull of integer points of a polyhedron and its metric characteristics. In: Proceedings of the First International Conference on Mathematical Algorithms, pp. 169–174. Nizhni Novgorod State University Publisher (1997). (in Russian)

8. Cook, W., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica 12(1), 27–37 (1992)

   Article  MathSciNet  MATH  Google Scholar 

9. Håstad, J.: On the size of weights for threshold gates. SIAM J. Discrete Math. 7(3), 484–492 (1994)

   Article  MathSciNet  Google Scholar 

10. Hayes, A.S., Larman, D.C.: The vertices of the knapsack polytope. Discrete Appl. Math. 6(2), 135–138 (1983)

    Article  MathSciNet  MATH  Google Scholar 

11. Hegedüs, T.: Geometrical concept learning and convex polytopes. In: Proceedings of the 7th Annual ACM Conference on Computational Learning Theory (COLT’94) pp. 228–236. New York, ACM Press (1994)

12. Hegedüs, T.: Generalized teaching dimensions and the query complexity of learning. In: Proceedings of the 8th Annual ACM Conference on Computational Learning Theory (COLT’95) pp. 108–117. New York, ACM Press (1995)

13. McMullen, P.: The maximum number of faces of a convex polytope. Mathematika 17, 179–184 (1991)

    Article  MathSciNet  MATH  Google Scholar 

14. Morgan, D.A.: Upper and lower bound results on the convex hull of integer points in polyhedra. Mathematika 38(2), 321–328 (1991)

    Article  MathSciNet  MATH  Google Scholar 

15. Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience, New York (1986)

    MATH  Google Scholar 

16. Shevchenko, V.N.: On the number of extreme points in integer programming. Kibernetika 2, 133–134 (1981)

    MathSciNet  MATH  Google Scholar 

17. Shevchenko, V.N., Zolotykh, N.Yu.: On complexity of deciphering threshold functions of \(k\)-valued logic. Russ. Math. Dokl. 362(5), 606–608 (1998)

18. Veselov, S.I.: A lower bound for the mean number of irreducible and extreme points in two discrete programming problems. Manuscript 61984, deposited at VINITI, Moscow (1984). (in Russian)

19. Veselov, S.I., Chirkov, A.Yu.: Some estimates for the number of vertices of integer polyhedra. J. Appl. Ind. Math. 2(4), 591–604 (2008)

20. Ziegler, G.M.: Lectures on Polytopes. Springer, Berlin (1995)

    Book  MATH  Google Scholar 

21. Zolotykh, N.Yu.: On the number of vertices in integer linear programming problems. arXiv:math/0611356 [math.CO] (2006)

22. Zolotykh, N.Yu., Chirkov, A.Y.: On the upper bound for cardinality of the minimal teaching set of a threshold function. Discrete Anal. Oper. Res. 19(5), 35–46 (2012). (in Russian)

23. Zolotykh, N.Yu., Shevchenko, V.N.: On complexity of deciphering threshold functions. Discrete Anal. Oper. Res. 2(3), 72–73 (1995). (in Russian)

24. Zolotykh, N.Yu., Shevchenko, V.N.: Estimating the complexity of deciphering a threshold functions in a \(k\)-valued logic. Comput. Math. Math. Phys. 39(2), 328–334 (1999)

Download references