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

DOI10.1016/0166-218X(84)90013-1zbMath0551.90033MaRDI QIDQ800816

R. Chandrasekaran, Arie Tamir

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmminimal cost reliability ratio spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Reliability, availability, maintenance, inspection in operations research (90B25)

Related Items (6)

A global optimization algorithm for solving the minimum multiple ratio spanning tree problem ⋮ On the complexity and approximation of the maximum expected value all-or-nothing subset ⋮ A Fourth bibliography of fractional programming ⋮ A fully polynomial time approximation scheme for minimum cost-reliability ratio problems ⋮ Element perturbation problems of optimum spanning trees with two-parameter objectives ⋮ On minimal cost-reliability ratio spanning trees and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Linear forms in two logarithms and Schneider's method
• Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games
• Minimal Cost-Reliability Ratio Spanning Tree
• A sharpening of the bounds for linear forms in logarithms III
• Linear forms in the logarithms of algebraic numbers (IV)

This page was built for publication: Polynomial testing of the query Is \(a^ b\geq c^ d?\) with application to finding a minimal cost reliability ratio spanning tree