×

On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. (English) Zbl 0915.68072

Summary: We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machine learning, operations research and pattern recognition. In the first class (MIN ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the others. In the second class (MIN RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both MIN ULR and MIN RVLS the four basic types of relational operators \(=\), \(\geqslant\), \(>\) and \(\neq\) are considered. While MIN RVLS with equations was mentioned to be NP-hard in M. R. Garey and D. S. Johnson [Computers and intractability. A guide to the theory of NP-completeness (1979; Zbl 0411.68039)], we established [in E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subystems of linear relations, Theoret. Comput. Sci. 147, No. 1, 181-210 (1995; Zbl 0884.68093)] that MIN ULR with equalities and inequalities are NP-hard even when restricted to homogeneous systems with bipolar coefficients. The latter problems have been shown hard to approximate [in S. Arora, L. Babai, J. Stern and Z. Sweedyk, J. Comput. Syst. Sci. 54, No. 2, 317-331, Art. No. SS971472 (1997; Zbl 0877.68067)]. In this paper we determine strong bounds on the approximability of various variants of MIN RVLS and MIN ULR, including constrained ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The various NP-hard versions turn out to have different approximability properties depending on the type of relations and the additional constraints, but none of them can be approximated within any constant factor, unless P=NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In particular, we disprove a conjecture of K. van Horn and T. Martinez [The minimum feature set problem, IEEE Trans. Neural Networks 7, 491-494 (1994)] regarding the existence of a polynomial-time algorithm to design linear classifiers (or perceptrons) that involve a close-to-minimum number of features.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Amaldi, E., On the complexity of training preceptrons, (Kohonen, T.; Mäkisara, K.; Simula, O.; Kangas, J., Artificial Neural Networks (1991), Elsevier: Elsevier Amsterdam), 55-60
[2] Amaldi, E., Complexity of problems related to training perceptrons, (Chaleyat-Maurel, M.; Cottrell, M.; Fort, J.-C., Actes du congrès “Aspects théoriques des réseaux de neurones”, Congrès Européen de Mathématiques. Actes du congrès “Aspects théoriques des réseaux de neurones”, Congrès Européen de Mathématiques, Paris (1992))
[3] Amaldi, E., From finding maximum feasible subsystems of linear systems to feedforward neural network design, (Ph.D. Thesis (1994), Department of Mathematics, Swiss Federal Institute of Technology: Department of Mathematics, Swiss Federal Institute of Technology Lausanne)
[4] Amaldi, E.; Kann, V., On the approximability of removing the smallest number of relations from linear systems to achieve feasibility, (Technical Report ORWP-6-94 (1994), Department of Mathematics, Swiss Federal Institute of Technology: Department of Mathematics, Swiss Federal Institute of Technology Lausanne)
[5] Amaldi, E.; Kann, V., The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoret. Comput. Sci., 147, 181-210 (1995) · Zbl 0884.68093
[6] Angluin, D.; Smith, C. H., Inductive inference: Theory and methods, ACM Comput. Surveys, 15, 237-269 (1983)
[7] Arora, S.; Babai, L.; Stern, J.; Sweedyk, Z., The hardness of approximate optima in lattices, codes, and systems of linear equations, (Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press. Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press, Silver Spring, MD (1993)), 724-733
[8] Arora, S.; Babai, L.; Stern, J.; Sweedyk, Z., The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. System Sci., 317-331 (1997) · Zbl 0877.68067
[9] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and hardness of approximation problems, (Proc. 33rd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press. Proc. 33rd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press, Silver Spring, MD (1992)), 14-23 · Zbl 0977.68539
[10] Bellare, M.; Goldwasser, S.; Lund, C.; Russell, A., Efficient probabilistically checkable proofs and applications to approximation, (Proc. 25th Ann. ACM Symp. on Theory of Comp., ACM. Proc. 25th Ann. ACM Symp. on Theory of Comp., ACM, New York (1993)), 294-304 · Zbl 1310.68083
[11] Bellare, M.; Goldreich, O.; Sudan, M., Free bits, PCPs and non-approximability—towards tight results, (Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press. Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press, Silver Spring, MD (1995)), 422-431 · Zbl 0938.68820
[12] Bennett, K. P.; Mangasarian, O. L., Robust linear programming discrimination of two linearly inseparable sets, Optimization Meth. Software, 1, 23-34 (1992)
[13] Chinneck, J., An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem, Ann. Math. Artificial Intelligence, 17, 127-144 (1996) · Zbl 0887.90112
[14] Chinneck, J., Feasibility and viability, (Gal, T.; Greenberg, H. J., Advances in sensitivity analysis and parametric programming (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 0903.90157
[15] Chinneck, J.; Dravnieks, E., Locating minimal infeasible constraint sets in linear programs, ORSA J. Comput., 3, 157-168 (1991) · Zbl 0755.90055
[16] Chvatal, V., Linear programming (1983), Freeman: Freeman New York · Zbl 0318.05002
[17] Crescenzi, P.; Kann, V., A compendium of NP optimization problems, (Technical Report SI/RR-95/02 (1995), Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”), The list is updated continuously. The latest version is available by anonymous ftp from nada.kth.se as Theory/Viggo-Kann/compendium.ps.Z.
[18] Crescenzi, P.; Kann, V.; Silvestri, R.; Trevisan, L., Structure in approximation classes, (Proc. 1st Internat. Conf. on Computing and Combinatorics. Proc. 1st Internat. Conf. on Computing and Combinatorics, Lecture Notes in Computer Science, vol. 959 (1995), Springer: Springer Berlin), 539-548
[19] Crescenzi, P.; Panconesi, A., Completeness in approximation classes, Inform. and Comput., 93, 2, 241-262 (1991) · Zbl 0734.68039
[20] Crescenzi, P.; Silvestri, R.; Trevisan, L., To weight or not to weight: Where is the question?, (Proc. 4th Israel Symp. on Theory of Computing and Systems, IEEE Comput. Soc. Press. Proc. 4th Israel Symp. on Theory of Computing and Systems, IEEE Comput. Soc. Press, Silver Spring, MD (1996)), 68-77
[21] Duda, R. O.; Hart, P. E., Pattern classification and scene analysis (1973), Wiley: Wiley New York · Zbl 0277.68056
[22] Edmonds, J., Redundancy and Helly for linear programming, Lecture Notes (1994)
[23] Even, G.; Naor, J.; Schieber, B.; Sudan, M., Approximating minimum feedback sets and multi-cuts in directed graphs, (Proc. 4th Internat. Conf. on Integer Prog, and Combinatorial Optimization. Proc. 4th Internat. Conf. on Integer Prog, and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 920 (1995), Springer: Springer Berlin), 14-28 · Zbl 0897.68078
[24] Feige, U., A threshold of \(In n\) for approximating set cover, (Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM. Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM, New York (1996)), 314-318 · Zbl 0922.68067
[25] Frean, M. R., A thermal perceptron learning rule, Neural Computation, 4, 946-957 (1992)
[26] Gallant, S. I., Perceptron-based learning algorithms, IEEE Trans. Neural Networks, 1, 179-191 (1990)
[27] Garey, M. R.; Johnson, D. S., Computers and Intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[28] Gleeson, J.; Ryan, J., Identifying minimally infeasible subsystems of inequalities, ORSA J. Computing, 3, 61-63 (1990) · Zbl 0752.90050
[29] Greenberg, H. J., Consistency, redundancy, and implied equalities in linear systems, Ann. Math. Artificial Intelligence, 17, 37-83 (1996) · Zbl 0887.90114
[30] Greenberg, H. J.; Murphy, F. H., Approaches to diagnosing infeasible linear programs, ORSA J. Computing, 3, 253-261 (1991) · Zbl 0753.90041
[31] Greer, R., Trees and hills: Methodology for maximizing functions of systems of linear relations, (volume 22 of Annals of Discrete Mathematics (1984), Elsevier: Elsevier Amsterdam) · Zbl 0642.90066
[32] Grigni, M.; Mirelli, V.; Papadimitriou, C. H., On the difficulty of designing good classifiers, (Proc. 2nd Internat. Conf. on Computing and Combinatorics. Proc. 2nd Internat. Conf. on Computing and Combinatorics, Lecture Notes in Computer Science, vol. 1090 (1996), Springer: Springer Berlin), 273-279 · Zbl 0959.68044
[33] Guieu, O.; Chinneck, J., Analyzing infeasible mixed-integer and integer linear programs, (Technical Report Technical Report SCE-96-05 (1996), Department of Systems and Computer Engineering, Carleton University: Department of Systems and Computer Engineering, Carleton University Ottawa, Canada) · Zbl 1034.90519
[34] Halldóroson, M. M., Approximating the minimum maximal independence number, Inform. Process. Lett., 46, 169-172 (1993) · Zbl 0778.68041
[35] Hassoun, M., Fundamentals of artificial neural networks (1995), MIT Press: MIT Press Cambridge, MA · Zbl 0850.68271
[36] Håstad, J., Clique is hard to approximate within \(n^{1−ε}\), (Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press. Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press, Silver Spring, MD (1996)), 627-636
[37] Håstad, J., Some optimal inapproximability results, (Proc. 29th Ann. ACM Symp. on Theory of Comp, ACM. Proc. 29th Ann. ACM Symp. on Theory of Comp, ACM, New York (1997)), 1-10 · Zbl 0963.68193
[38] Höffgen, K-U.; Simon, H-U.; van Horn, K., Robust trainability of single neurons, J. Comput. System Sci., 50, 114-125 (1995) · Zbl 0939.68771
[39] Johnson, D. S.; Preparata, P. P., The densest hemisphere problem, Theoret. Comput. Sci., 6, 93-107 (1978) · Zbl 0368.68053
[40] Kann, V., On the Approximability of NP-complete Optimization Problems, (Ph.D. Thesis (1992), Department of Numerical Analysis and Computing Science, Royal Institute of Technology: Department of Numerical Analysis and Computing Science, Royal Institute of Technology Stockholm)
[41] Kann, V., Polynomially bounded minimization problems that are hard to approximate, Nordic J. Computing, 1, 317-331 (1994) · Zbl 0817.68082
[42] Kann, V., Strong lower bounds on the approximability of some NPO PB-complete maximization problems, (Proc. 20th Ann. Mathematical Foundations of Comput. Sci.. Proc. 20th Ann. Mathematical Foundations of Comput. Sci., Lecture Notes in Computer Science, vol. 969 (1995), Springer: Springer Berlin), 227-236 · Zbl 1193.68120
[43] Kann, V.; Panconesi, A., Hardness of approximation, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley New York), Ch. 2 · Zbl 1068.90514
[44] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[45] Kearns, M.; Valiant, L., Cryptographic limitations on learning boolean formulae and finite automata, J. ACM, 41, 67-95 (1994) · Zbl 0807.68073
[46] Kearns, M.; Vazirani, U., An introduction to Computational Learning Theory (1994), MIT Press: MIT Press Cambridge, MA
[47] Khanna, S.; Sudan, M.; Trevisan, L., Constraint satisfaction: The approximability of minimization problems, (Proc. 12th Annual IEEE Conf. Comput. Complexity. IEEE Comput. Soc., Press. Proc. 12th Annual IEEE Conf. Comput. Complexity. IEEE Comput. Soc., Press, Silver Spring, MD (1997)), 282-296
[48] Koehler, G. J., Linear discriminant functions determined by genetic search, ORSA J. Computing, 3, 345-357 (1991) · Zbl 0775.68041
[49] Koehler, G. J.; Erenguc, S. S., Minimizing misclassifications in linear discriminant analysis, Decision Sci., 21, 63-85 (1990)
[50] Lin, J.-H.; Vitter, J. S., Complexity results on learning by neural nets, Mach. Learning, 6, 211-230 (1991)
[51] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 960-981 (1994) · Zbl 0814.68064
[52] Mangasarian, O. L., Misclassification minimization, J. Global Optimization, 5, 309-323 (1994) · Zbl 0814.90081
[53] Marchand, M.; Golea, M., On learning simple neural concepts: from halfspace intersections to neural decision lists, Network: Computation in Neural Systems, 4, 67-85 (1993)
[54] McLachlan, G. J., Discriminant analysis and statistical pattern recognition (1992), Wiley: Wiley New York
[55] Minsky, M. L.; Papert, S., Perceptrons: An introduction to computational Geometry (1988), MIT Press: MIT Press Cambridge, MA, expanded edition · Zbl 0197.43702
[56] Papadimitriou, C. H.; Steiglitz, K., Combinatorial optimization, Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[57] Parker, M., A set covering approach to infeasibility analysis of linear programming problems and related issues, (Ph.D. Thesis (1995), Department of Mathematics, University of Colorado: Department of Mathematics, University of Colorado Denver)
[58] Parker, M.; Ryan, J., Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Ann. Math. Artificial Intelligence, 17, 107-126 (1996) · Zbl 0889.90110
[59] Rivest, R., Cryptography, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A: Algorithms and complexity (1990), Elsevier: Elsevier Amsterdam), 717-755 · Zbl 0900.68255
[60] Sankaran, J., A note on resolving infeasibility in linear programs by constraint relaxation, Oper. Res. Lett., 13, 19-20 (1993) · Zbl 0771.90068
[61] Schrijver, A., Theory of linear and integer programming, (Interscience series in discrete mathematics and optimization (1986), Wiley: Wiley New York) · Zbl 0665.90063
[62] Seymour, P., Packing directed circuits fractionally, Combinatorica, 15, 281-288 (1995) · Zbl 0826.05031
[63] Valiant, L. G., A theory of the learnable, Communications of ACM, 27, 1134-1142 (1984) · Zbl 0587.68077
[64] van Horn, K.; Martinez, T., The minimum feature set problem, (Technical Report CS-92-8 (1992), Computer Science Department, Brigham Young University: Computer Science Department, Brigham Young University Provo) · Zbl 0900.68370
[65] van Horn, K.; Martinez, T., The minimum feature set problem, IEEE Trans. Neural Networks, 7, 491-494 (1994) · Zbl 0900.68370
[66] Warmack, R. E.; Gonzalez, R. C., An algorithm for optimal solution of linear inequalities and its application to pattern recognition, IEEE Trans. Comput., 22, 1065-1075 (1973) · Zbl 0269.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.