Bibliography on MaxFS

[ Home | People | Papers | Software | Instances | Links ]

This list is constantly updated.
If you want to give us comment or add references, please send an email to


  1. E. Aarts and J. Korst.
    Simulated annealing and Boltzmann machines.
    John Wiley & Sons, Chichester, 1989.

  2. C. C. Aggarwal, R. K. Ahuja, J. Hao, and J. B. Orlin.
    Diagnosing infeasibilities in network flow problems.
    Math. Programming A, 81:263-280, 1998.

  3. E. Amaldi.
    On the complexity of training perceptrons.
    In T. Kohonen, K. Mäkisara, O. Simula, and J. Kangas, editors, Artificial Neural Networks, pages 55-60, Amsterdam, 1991. Elsevier science publishers B.V.

  4. E. Amaldi.
    Complexity of problems related to training perceptrons.
    In M. Chaleyat-Maurel, M. Cottrell, and J.-C. Fort, editors, Actes du congrès ``Aspects théoriques des réseaux de neurones'', Congrès Européen de Mathématiques. Paris, July 1992.

  5. E. Amaldi.
    From finding maximum feasible subsystems of linear systems to feedforward neural network design.
    PhD thesis, Dep. of Mathematics, EPF-Lausanne, October 1994.

  6. E. Amaldi and V. Kann.
    The complexity and approximability of finding maximum feasible subsystems of linear relations.
    Technical Report ORWP-11-93, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, 1993.
    To be published in Theoret. Comput. Sci.

  7. E. Amaldi and V. Kann.
    The complexity and approximability of finding maximum feasible subsystems of linear relations.
    Technical Report TRITA-NA-9313, ISSN 0348-2952, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1993.
    To be published in Theoret. Comput. Sci.

  8. E. Amaldi and V. Kann.
    The complexity and approximability of finding maximum feasible subsystems of linear relations.
    Technical Report ORWP-11-93, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne and Technical Report TRITA-NA-9313, ISSN 0348-2952, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1993.
    To be published in Theoret. Comput. Sci.

  9. E. Amaldi and V. Kann.
    On the approximability of finding maximum feasible subsystems of linear systems.
    In Proc. 11th Ann. Symp. Theoretical Aspects of Comput. Sci., pages 521-532. Springer-Verlag, 1994.
    Lecture Notes in Comput. Sci. 775.

  10. E. Amaldi and V. Kann.
    On the approximability of removing the smallest number of relations from linear systems to achieve feasibility.
    Technical Report ORWP-6-94, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, 1994.

  11. E. Amaldi and V. Kann.
    The complexity and approximability of finding maximum feasible subsystems of linear relations.
    Theoret. Comput. Sci., 147:181-210, 1995.

  12. E. Amaldi and V. Kann.
    On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems.
    Theoret. Comput. Sci., 209:237-260, 1998.

  13. E. Amaldi and M. Mattavelli.
    The MIN PFS problem and piecewise linear model estimation.
    Discrete Appl. Math., 118:115-143, 2002.

  14. E. Amaldi, M. E. Pfetsch, and L. E. Trotter Jr.
    On the maximum feasible subsystem problem, IISs and IIS-hypergraphs.
    Math. Programming A, 95:533-554, 2003.
    Preliminary version: Some structural and algorithmic properties of the maximum feasible subsystem problem, Proceedings of the 10th Integer Programming and Combinatorial Optimization conference (G. Cornuéjols, R. Burkard and G. Woeginger, eds.), LNCS 1610, Springer-Verlag, 1999, pp. 45-59.

  15. E. Amaldi, M. E. Pfetsch, and L. E. Trotter, Jr.
    Some structural and algorithmic properties of the maximum feasible subsystem problem.
    In G. Cornuéjols, R. Burkard, and G. Woeginger, editors, Proceedings of the 10th Integer Programming and Combinatorial Optimization conference (IPCO'99), pages 45-59. Springer-Verlag, 1999.
    Lecture Notes in Comput. Sci. 1610.

  16. K. P. Bennett and E. Bredensteiner.
    A parametric optimization method for machine learning.
    INFORMS J. Comput., 9:311-318, 1997.

  17. K. P. Bennett and O. L. Mangasarian.
    Robust linear programming discrimination of two linearly inseparable sets.
    Optimization Methods and Software, 1:23-34, 1992.

  18. C. L. Blake and C. J. Merz.
    UCI repository of machine learning databases.
    available at the UCI Machine Learning Repository.

  19. H. D. Block and S. A. Levin.
    On the boundedness of an iterative procedure for solving a system of linear inequalities.
    In Proceedings of AMS, pages 229-235, 1970.

  20. P. S. Bradley, U. M. Fayyad, and O. L. Mangasarian.
    Mathematical programming for data mining: Formulations and challenges.
    INFORMS J. Comput., 11:217-238, 1999.

  21. Y. Censor and S. A. Zenios.
    Parallel Optimization: Theory, algorithms and applications.
    Oxford University Press, 1997.

  22. N. Chakravarti.
    Some results concerning post-infeasibility analysis.
    Eur. J. Oper. Res., 73:139-143, 1994.

  23. J. W. Chinneck.
    Computer codes for the analysis of infeasible linear programs.
    J. Oper. Res. Soc., 47:61-72, 1996.

  24. J. W. Chinneck.
    An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem.
    Ann. Math. Artificial Intelligence, 17:127-144, 1996.

  25. J. W. Chinneck.
    Feasibility and viability.
    In T. Gál and H.J. Greenberg, editors, Advances in Sensitivity Analysis and Parametric Programming. Kluwer Academic Publishers, 1997.

  26. J. W. Chinneck.
    Finding a useful subset of constraints for analysis in an infeasible linear program.
    INFORMS J. Comput., 9(2):164-174, 1997.

  27. J. W. Chinneck.
    Fast heuristics for the maximum feasible subsystem problem.
    INFORMS J. Comput., 13(3):210-223, 2001.

  28. J. W. Chinneck and E. Dravnieks.
    Locating minimal infeasible constraint sets in linear programs.
    ORSA J. Comput., 3:157-168, 1991.

  29. K. Fan.
    On systems of linear inequalities.
    In H. W. Kuhn and A. W. Tucker, editors, Linear Inequalities and Related Systems, number 38 in Ann. of Math. Stud., pages 99-156. Princeton University Press, NJ, 1956.

  30. M. Frean.
    A ``thermal'' perceptron learning rule.
    Neural Comput., 4(6):946-957, 1992.

  31. N. Freed and F. Glover.
    Simple but powerful goal programming models for discriminant problems.
    Eur. J. Oper. Res., 7:44-60, 1981.

  32. K. Fukuda and V. Rosta.
    Exact parallel algorithms for the location depth and the maximum feasible subsystem problems.
    In C. A. Floudas and P. M. Pardalos, editors, Frontiers in Global Optimization. Kluwer Academic Publishers, 2003.
    To appear.

  33. W. V. Gehrlein.
    General mathematical programming formulations for the statistical classification problem.
    Oper. Res. Lett., 5:299-304, 1986.

  34. J. Gleeson and J. Ryan.
    Identifying minimally infeasible subsystems of inequalities.
    ORSA J. Comput., 2(1):61-63, 1990.

  35. F. Glover.
    Improved linear and integer programming models for discriminant analysis.
    Decision Sciences, 21:771-785, 1990.

  36. J. L. Goffin.
    The relaxation method for solving systems of linear inequalities.
    Math. of Oper. Res., 5:388-414, 1980.

  37. H. J. Greenberg.
    Consistency, redundancy, and implied equalities in linear systems.
    Ann. Math. Artificial Intelligence, 17:37-83, 1996.

  38. H. J. Greenberg and F. H. Murphy.
    Approaches to diagnosing infeasible linear programs.
    ORSA J. Comput., 3:253-261, 1991.

  39. R. Greer.
    Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations, volume 22 of Ann. Discrete Math.
    Elsevier science publishing company, Amsterdam, 1984.

  40. O. Guieu and J. W. Chinneck.
    Analyzing infeasible mixed-integer and integer linear programs.
    Technical Report Technical report SCE-96-05, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada, 1996.

  41. M. M. Halldórsson.
    Approximating via partitioning.
    Technical Report IS-RR-95-0003F, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, 1995.

  42. D. J. Hand.
    Discrimination and classification.
    John Wiley & Sons, New York, 1981.

  43. G. J. Koehler.
    Improper linear discriminant classifiers.
    Eur. J. Oper. Res., 50:188-198, 1991.

  44. G. J. Koehler.
    Linear discriminant functions determined by genetic search.
    ORSA J. Comput., 3:345-357, 1991.

  45. G. J. Koehler and S. S. Erenguc.
    Minimizing misclassifications in linear discriminant analysis.
    Decision Sciences, 21:63-85, 1990.

  46. E. K. Lee, R. J. Gallagher, and M. Zaider.
    Planning implants of radionuclides for the treatment of prostate cancer: An application of mixed integer programming.
    Optima, 61:1-7, 1999.

  47. O. L. Mangasarian.
    Misclassification minimization.
    J. Global Optim., 5(4):309-323, 1994.

  48. O. L. Mangasarian.
    Machine learning via polyhedral concave minimization.
    In H. Fischer, B. Riedmueller, and S. Schaeffler, editors, Applied Mathematics and Parallel Computing -Festschrift for Klaus Ritter, pages 175-188. Physica-Verlag, 1996.

  49. M. Marchand and M. Golea.
    An approximate algorithm to find the largest linearly separable subset of training examples.
    In Proc. of 1993 Ann. Meeting of the International Neural Network Society, pages 556-559. INNS Press, 1993.

  50. M. Marchand and M. Golea.
    On learning simple neural concepts: from halfspace intersections to neural decision lists.
    Network: Computation in Neural Systems, 4:67-85, 1993.

  51. M. Mattavelli, V. Noel, and E. Amaldi.
    An efficient line detection algorithm based on a new combinatorial optimization techniques.
    In Proceedings of the 1998 International Conference on Image Processing (ICIP98), Chicago, Illinois, number 3, pages 65-69. IEEE Press, 1998.

  52. M. Mattavelli, V. Noel, and E. Amaldi.
    Fast line detection algorithms based on combinatorial optimization.
    In C. Arcelli, L.P. Cordella, and G. Sanniti di Baja, editors, Proceedings of the 4th International Workshop on Visual Form, LCNS 2059, pages 410-419. Springer-Verlag, 2001.

  53. G. J. McLachlan.
    Discriminant analysis and statistical pattern recognition.
    John Wiley & Sons, New York, 1992.

  54. J. Meller, M. Wagner, and R. Elber.
    Maximum feasibility guideline in the design and analysis of protein folding potentials.
    J. of Computational Chemistry, 23:111-118, 2002.

  55. J. Meller, M. Wagner, and R. Elber.
    Solving huge linear programming problems for the design of protein folding potentials.
    To appear in Math. Programming A, 2002.

  56. M. L. Minsky and S. Papert.
    Perceptrons: An introduction to computational Geometry.
    MIT Press, Cambridge, MA, 1988.
    Expanded edition.

  57. N. E. Mnëv.
    The universality theorems on the classification problem of configuration varieties and convex polytopes varieties.
    In O. Ya Viro, editor, Topology and Geometry - Rohlin Seminar, number 1346 in Lecture Notes in Math., pages 527-543. Springer-Verlag, 1988.

  58. T. S. Motzkin.
    Beiträge zur Theorie der Linearen Ungleichungen.
    PhD thesis, University of Basel, 1933.
    English version: ``Contributions to the Theory of Linear Inequalities,' translated by D. R. Fulkerson, in ``Theodore S. Motzkin: Selected Papers'' (D. Cantor, B. Gordon and B. Rothschild, eds.), Birkhäuser, Boston, 1983.

  59. A. Nedic and D. Bertsekas.
    Incremental subgradient methods for nondifferentiable optimization.
    SIAM J. on Optimization, 12:109-138, 2001.

  60. K. Park, M. Vendruscolo, and E. Domany.
    Toward an energy function for the contact map representation of proteins.
    PROTEINS: Structure, Function, and Genetics, 40:237-248, 2000.

  61. M. Parker.
    A set covering approach to infeasibility analysis of linear programming problems and related issues.
    PhD thesis, Dep. of Mathematics, University of Colorado at Denver, 1995.

  62. M. Parker and J. Ryan.
    Finding the minimum weight IIS cover of an infeasible system of linear inequalities.
    Ann. Math. Artificial Intelligence, 17:107-126, 1996.

  63. M. E. Pfetsch.
    Examples of generalized antiweb facets.
    Electronic Geometry Models, No. 2000.09.029 (2000), available at EG-models.

  64. M. E. Pfetsch.
    The maximum feasible subsystem problem and vertex-facet incidences of polyhedra.
    PhD thesis, Dep. of Mathematics, Technische Universität Berlin, October 2002.

  65. J. Richter-Gebert.
    Realization Spaces of Polytopes.
    Number 1643 in Lecture Notes in Math. Springer-Verlag, 1996.

  66. F. Rossi, A. Sassano, and S. Smriglio.
    Models and algorithms for terrestrial digital broadcasting.
    Technical Report 6, Dipartimento di Matematica Pura e Applicata, Università degli Studi di L'Aquila, Italy, 1999.

  67. F. Rossi, A. Sassano, and S. Smriglio.
    Models and algorithms for terrestrial digital broadcasting.
    Ann. of Oper. Res., (107):267-283, 2001.

  68. J. Ryan.
    Transversals of IIS-hypergraphs.
    Congr. Numer., 81:17-22, 1991.

  69. J. Ryan.
    IIS-hypergraphs.
    SIAM J. Discrete Math., 9:643-653, 1996.

  70. P. Sadegh.
    A maximum feasible subset algorithm with application to radiation therapy.
    Proceedings of the 18th American Control Conference, San Diego, California, pages 405-408, 1999.

  71. M. Sánchez-García, M. I. Sobrón, and B. Vitoriano.
    On the set covering polytope: Facets with coefficients in {0,1,2,3}.
    Ann. of Oper. Res., 81:343-356, 1998.

  72. J. Sankaran.
    A note on resolving infeasibility in linear programs by constraint relaxation.
    Oper. Res. Lett., 13:19-20, 1993.

  73. H. D. Sherali.
    Tight relaxations for nonconvex optimization problems using the reformulation-linearization/convexification technique (RLT).
    In P. M. Pardalos and H. E. Romeijn, editors, Handbook of Global Optimization, volume 2, pages 1-63. Kluwer Academic Publishers, 2002.

  74. H. D. Sherali and W. P. Adams.
    Computational advances using the reformulation-linearization technique (RLT) to solve discrete and continuous nonconvex problems.
    Optima, 49:1-6, 1996.

  75. A. Stam and E. A. Joachimsthaler.
    A comparison of a robust mixed-integer approach to existing methods for establishing classification rules for the discriminant problem.
    Eur. J. Oper. Res., 46:113-122, 1990.

  76. M. Tamiz, S.J. Mardle, and D.F. Jones.
    Detecting IIS in infeasible linear programmes using techniques from goal programming.
    Comput. Oper. Res., 23(2):113-119, 1996.

  77. J. Telgen.
    On relaxation methods for systems of linear inequalities.
    Eur. J. Oper. Res., 9:184-189, 1982.

  78. J. N. M. van Loon.
    Irreducibly inconsistent systems of linear inequalities.
    Eur. J. Oper. Res., 8:282-288, 1981.

  79. M. Vendruscolo, L. A. Mirny, E. I. Shakhnovich, and E. Domany.
    Comparison of two optimization methods to derive energy parameters for protein folding: perceptron and Z score.
    PROTEINS: Structure, Function, and Genetics, 41:192-201, 2000.

  80. R. E. Warmack and R. C. Gonzalez.
    An algorithm for optimal solution of linear inequalities and its application to pattern recognition.
    IEEE Trans. on Information Theory, 12:1065-1075, 1973.

This page is maintained by Pietro Belotti.