×

Polynomial testing of the query ”Is \(a^ b\geq c^ d?''\) with application to finding a minimal cost reliability ratio spanning tree. (English) Zbl 0551.90033

Given integers a, b, c, d, we present a polynomial algorithm for the query ”is \(a^ b\geq c^ d?''\). The result is applied to yield a polynomial algorithm for the minimal cost reliability ratio spanning tree problem.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, A., Linear forms in the logarithms of algebraic numbers IV, Mathematika, 15, 204-216 (1968) · Zbl 0169.37802
[2] Baker, A., A sharpening of the bounds for linear forms in logarithms III, Acta Arithmetica, 27, 247-252 (1974) · Zbl 0301.10030
[3] Baker, A., Transcendental Number Theory (1975), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0297.10013
[4] Baker, A., The theory of linear forms in logarithms, (Baker, A.; Masser, D., Transcendence Theory: Advances and Applications (1977), Academic Press: Academic Press London and New York) · Zbl 0361.10028
[5] Bers, L., Calculus (1969), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York
[6] Chandrasekaran, R.; Aneja, Y. P.; Nair, K. P.K., Minimal cost reliability ratio spanning tree, Annals Discrete Math., 11, 53-60 (1981) · Zbl 0469.90083
[7] R. Chandrasekaran and A. Tamir, Optimization problems with algebraic solutions: quadratic fractional programs and ratio games, Math. Programming, to appear.; R. Chandrasekaran and A. Tamir, Optimization problems with algebraic solutions: quadratic fractional programs and ratio games, Math. Programming, to appear. · Zbl 0571.90086
[8] Feldman, N. I., Math. USSR Sbornik, 6, 393-406 (1968), English translation in
[9] Frank, H.; Frisch, I. T., Communication, Transmission and Transportation Networks (1971), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0281.94012
[10] Gelfond, A. O., On the approximation of transcendental numbers by algebraic numbers, Doklady Akad. Nauk SSSR, 2, 177-182 (1935)
[11] Gusfield, D. M., Sensitivity analysis for combinatorial optimization (May 1980), Electronics Research Laboratory, College of Engineering, University of California: Electronics Research Laboratory, College of Engineering, University of California Berkeley, (Memo. No. UCB/ERL M80/22)
[12] Mignotte, M.; Waldschmidt, M., Linear forms in two logarithms and Schneider’s Method, Math. Ann., 231, 241-267 (1978) · Zbl 0349.10029
[13] Morduchai-Boltovskoj, D., Sur le logarithme d’un nombre algebrique, C.R. Acad. Sci., 176, 724-727 (1923), (Paris) · JFM 49.0133.02
[14] Prim, R. C., Shortest connected networks and some generalizations, Bell Syst. Tech. J., 36, 1389-1401 (1957)
[15] Yao, A. C., An \(O(∣E\)∣log log∣\(V\)∣) algorithm for finding minimum spanning tree, Inform. Process. Lett., 4, 21-23 (1975)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.