nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Binary Solutions to Some Systems of Linear Equations

verfasst von : Alexandr V. Seliverstov

Erschienen in: Optimization Problems and Their Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A point is called binary if its coordinates are equal to either zero or one. It is well known that it is hard to find a binary solution to the system of linear equations whose coefficients are integers with small absolute values. The aim of the article is to propose an effective probabilistic reduction from the system to the unique equation when there is a small difference between the number of binary solutions to the first equation and the number of binary solutions to the system. There exist nontrivial examples of linear equations with small positive coefficients having a small number of binary solutions in high dimensions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Accuracy Estimates for One Regularization Method in Linear Programming

Nächstes Kapitel Variant of the Cutting Plane Method with Approximation of the Set of Constraints and Auxiliary Functions Epigraphs

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

Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5(2), 266–277 (1957)MathSciNetCrossRef

Smolev, V.V.: On an approach to the solution of a Boolean linear equation with positive integer coefficients. Discrete Math. Appl. 3(5), 523–530 (1993). https://doi.org/10.1515/dma.1993.3.5.523MathSciNetCrossRefMATH

Tamir, A.: New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems. Oper. Res. Lett. 37(5), 303–306 (2009). https://doi.org/10.1016/j.orl.2009.05.003MathSciNetCrossRefMATH

Koiliaris, K., Xu, C.: A faster pseudopolynomial time algorithm for subset sum. In: SODA 2017 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1062–1072. Society for Industrial and Applied Mathematics, Philadelphia (2017)

Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: SODA 2017 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1073–1084. Society for Industrial and Applied Mathematics, Philadelphia (2017)

Margulies, S., Onn, S., Pasechnik, D.V.: On the complexity of Hilbert refutations for partition. J. Symbolic Comput. 66, 70–83 (2015). https://doi.org/10.1016/j.jsc.2013.06.005MathSciNetCrossRefMATH

Chistov, A.L.: An improvement of the complexity bound for solving systems of polynomial equations. J. Math. Sci. 181(6), 921–924 (2012). https://doi.org/10.1007/s10958-012-0724-4MathSciNetCrossRefMATH

Jeronimo, G., Sabia, J.: Sparse resultants and straight-line programs. J. Symbolic Comput. 87, 14–27 (2018). https://doi.org/10.1016/j.jsc.2017.05.005MathSciNetCrossRefMATH

10.

Latkin, I.V., Seliverstov, A.V.: Computational complexity of fragments of the theory of complex numbers. Bull. Karaganda Univ. Math. 1, 47–55 (2015). (In Russian). http://vestnik.ksu.kz

11.

Seliverstov, A.V.: On tangent lines to affine hypersurfaces. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki 27(2), 248–256 (2017). (In Russian). https://doi.org/10.20537/vm170208MathSciNetCrossRef

12.

Kolokolov, A.A., Zaozerskaya, L.A.: Finding and analysis of estimation of the number of iterations in integer programming algorithms using the regular partitioning method. Russian Math. (Iz. VUZ) 58(1), 35–46 (2014). https://doi.org/10.3103/S1066369X14010046

13.

Håstad, J., Rossman, B., Servedio, R.A., Tan, L.-Y.: An average-case depth hierarchy theorem for Boolean circuits. J. ACM 64(5), 35 (2017). https://doi.org/10.1145/3095799MathSciNetCrossRef

14.

Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277–292 (1974). https://doi.org/10.1145/321812.321823MathSciNetCrossRef

15.

Bansal, N., Garg, S., Nederlof, J., Vyas, N.: Faster space-efficient algorithms for subset sum and k-sum. In: STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 198–209 ACM, New York (2017). https://doi.org/10.1145/3055399.3055467

16.

Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: STOC 2010 Proceedings of the Forty-second ACM Symposium on Theory of Computing, pp. 321–330. ACM, New York (2010). https://doi.org/10.1145/1806689.1806735

17.

Gál, A., Jang, J.-T., Limaye, N., Mahajan, M., Sreenivasaiah, K.: Space-efficient approximations for Subset Sum. ACM Trans. Comput. Theory 8(4), 16 (2016). https://doi.org/10.1145/2894843MathSciNetCrossRef

18.

Williamson, J.: Determinants whose elements are 0 and 1. Am. Math. Monthly 53(8), 427–434 (1946)MathSciNetCrossRef

19.

Alon, N., Vũ, V.H.: Anti-Hadamard matrices, coin weighing, threshold gates and indecomposable hypergraphs. J. Comb. Theory A 79(1), 133–160 (1997). https://doi.org/10.1006/jcta.1997.2780MathSciNetCrossRef

20.

Babai, L., Hansen, K.A., Podolskii, V.V., Sun, X.: Weights of exact threshold functions. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 66–77. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_8CrossRefMATH

21.

Gorbunov, K.Yu., Seliverstov, A.V., Lyubetsky, V.A.: Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube. Probl. Inform. Transm. 48(2), 185–192 (2012). https://doi.org/10.1134/S0032946012020081MathSciNetCrossRef

22.

Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: STOC 2014 Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 194–202. ACM, New York (2014). https://doi.org/10.1145/2591796.2591858

23.

Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980). https://doi.org/10.1145/322217.322225MathSciNetCrossRef

24.

Bacher, A., Bodini, O., Hwang, H.-K., Tsai, T.-H.: Generating random permutations by coin-tossing: classical algorithms, new analysis, and modern implementation. ACM Trans. Algorithms 13(2), 24 (2017). https://doi.org/10.1145/3009909

25.

Beresnev, V.L., Melnikov, A.A.: An upper bound for the competitive location and capacity choice problem with multiple demand scenarios. J. Appl. Ind. Math. 11(4), 472–480 (2017). https://doi.org/10.1134/S1990478917040020CrossRef

Titel: Binary Solutions to Some Systems of Linear Equations
verfasst von: Alexandr V. Seliverstov
Verlag: Springer International Publishing
Buch: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"