Approximation algorithms for combinatorial fractional programming problems

DOI10.1007/BF02591737zbMath0616.90078OpenAlexW2054058796MaRDI QIDQ4726063

Naoki Katoh, Satoru Hashizume, Masao Fukushima, Toshihide Ibaraki

Publication date: 1987

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02591737

zbMATH Keywords

approximate solutionparametrized linear objective function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fractional programming (90C32) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Approximating a class of combinatorial problems with rational objective function, Capacity Constraints Across Nests in Assortment Optimization Under the Nested Logit Model, Hybrid column generation for large-size covering integer programs: application to transportation planning, Fractional 0-1 programming: applications and algorithms, Ratio combinatorial programs, The inverse-parametric knapsack problem, Approximation algorithms for feasible cut and multicut problems, A Fourth bibliography of fractional programming, Capacitated assortment and price optimization for customers with disjoint consideration sets, On the tightness of an LP relaxation for rational optimization and its applications, A parametric approach to integer linear fractional programming: Newton's and hybrid-Newton methods for an optimal road maintenance problem, Feature selection for consistent biclustering via fractional 0-1 programming, Approximation algorithms for fractional knapsack problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fractional programming: Applications and algorithms
• Combinatorial Optimization with Rational Objective Functions
• Duality and Sensitivity Analysis for Fractional Programs
• Minimal ratio spanning trees
• Fractional knapsack problems
• Combinatorial Problems: Reductibility and Approximation
• Parametric approaches to fractional programs
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• On Nonlinear Fractional Programming
• Fractional programming