The complexity of minimum ratio spanning tree problems

DOI10.1007/s10898-004-5119-8zbMath1082.90103OpenAlexW2044266092MaRDI QIDQ2574099

Susan W. Palocsay, Christopher C. Skiscim

Publication date: 16 November 2005

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-004-5119-8

zbMATH Keywords

Combinatorial optimizationNP-hardFractional programming

Mathematics Subject Classification ID

Fractional programming (90C32) Combinatorial optimization (90C27)

Related Items (5)

Approximating a class of combinatorial problems with rational objective function ⋮ A global optimization algorithm for solving the minimum multiple ratio spanning tree problem ⋮ Fractional 0-1 programming: applications and algorithms ⋮ A sixth bibliography of fractional programming ⋮ The maximum ratio clique problem

Cites Work

• Hyperbolic 0-1 programming and query optimization in information retrieval
• Minimal ratio spanning trees
• On Nonlinear Fractional Programming
• A Class of Fractional Programming Problems
• Minimum spanning trees with sums of ratios.

This page was built for publication: The complexity of minimum ratio spanning tree problems