Skip to main content
SpringerLink
Log in

Combinatorial optimization problems related to the committee polyhedral separability of finite sets

  • Mathematical Programming
  • Published:
Proceedings of the Steklov Institute of Mathematics Aims and scope Submit manuscript

Abstract

In the paper, the computational and approximational complexity of the minimal affine separating committee problem, as well as of some important special cases of this problem, is investigated.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. I. Eremin and Vl. D. Mazurov, Nonstationary Processes of Mathematical Programming (Nauka, Moscow, 1979) [in Russian].

    MATH  Google Scholar 

  2. I. I. Eremin, Systems of Linear Inequalities and Linear Optimization (Izd. UrO RAN, Yekaterinburg, 2007) [in Russian].

    MATH  Google Scholar 

  3. F. Rosenblatt, IEEE Trans. Appl. Industry 83(74), 285 (1964).

    Article  Google Scholar 

  4. A. L. Blum and R. L. Rivest, Neural Networks 5, 117 (1992).

    Article  Google Scholar 

  5. J. H. Lin and J. S. Vitter, Machine Learning 6, 211 (1991).

    Google Scholar 

  6. N. Megiddo, Discrete and Computational Geometry 3, 325 (1988).

    Article  MATH  MathSciNet  Google Scholar 

  7. M. Yu. Khachai, Dokl. RAN 406(6), 742 (2006).

    MathSciNet  Google Scholar 

  8. M. Yu. Khachai, Tavrichesk. Vestn. Inform. Mat. 1, 34 (2006).

    Google Scholar 

  9. Vl. D. Mazurov, Kybernetika 3, 140 (1971).

    MathSciNet  Google Scholar 

  10. I. Dinur, O. Regev, and C. Smyth, in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November, 2002.

  11. Vl. D. Mazurov, M. Yu. Khachai, and A. I. Rybin, Proc. Steklov Inst. Math., Suppl. 1, 67 (2002).

    MathSciNet  Google Scholar 

  12. N. Megiddo and A. Tamir, Operations Research Letters 1(5), 194 (1982).

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Mechanics, Ural Division of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russia

    Vl. D. Mazurov, M. Yu. Khachay & M. I. Poberii

Authors
  1. Vl. D. Mazurov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Yu. Khachay
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. I. Poberii
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Original Russian Text © Vl.D.Mazurov, M.Yu. Khachay, M.I. Poberii, 2008, published in Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2008, Vol. 14, No. 2.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mazurov, V.D., Khachay, M.Y. & Poberii, M.I. Combinatorial optimization problems related to the committee polyhedral separability of finite sets. Proc. Steklov Inst. Math. 263 (Suppl 2), 93–107 (2008). https://doi.org/10.1134/S0081543808060102

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0081543808060102

Keywords

Search

Navigation