Approximation algorithms for combinatorial fractional programming problems

DOI10.1007/BF02591737MaRDI QIDQ4726063zbMATH OpenOpenAlexFDO

Authors Satoru Hashizume, Masao Fukushima, Naoki Katoh, 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

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

Recommendations

• A combined algorithm for fractional programming
• An \(\varepsilon\)-approximation algorithm for a class of fractional programs
• Approximation algorithms for fractional knapsack problems
• scientific article; zbMATH DE number 1302174
• A polynomial time approximation algorithm for linear fractional programs
• A fully polynomial time approximation algorithm for generalized fractional programs
• Algorithms for generalized fractional programming
• An algorithm for generalized fractional programs
• An efficient algorithm for solving a class of fractional programming problems
• An \(\varepsilon\)-approximation algorithm for generalized fractional programs

Cites work

• scientific article; zbMATH DE number 3848997 (Why is no real title available?)
• scientific article; zbMATH DE number 3717131 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial Problems: Reductibility and Approximation
• Duality and Sensitivity Analysis for Fractional Programs
• Fractional knapsack problems
• Fractional programming
• Fractional programming: Applications and algorithms
• Minimal ratio spanning trees
• On Nonlinear Fractional Programming
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• Parametric approaches to fractional programs

Cited in

(17)

• The inverse-parametric knapsack problem
• Feature selection for consistent biclustering via fractional 0-1 programming
• Fractional 0-1 programming: applications and algorithms
• A parametric approach to integer linear fractional programming: Newton's and hybrid-Newton methods for an optimal road maintenance problem
• Ratio combinatorial programs
• Approximation algorithms for feasible cut and multicut problems
• 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
• A Fourth bibliography of fractional programming
• On the tightness of an LP relaxation for rational optimization and its applications
• Approximation algorithms for fractional knapsack problems
• Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems
• A polynomial algorithm for a class of 0-1 fractional programming problems involving composite functions, with an application to additive clustering
• Approximating Rational Objectives Is as Easy as Approximating Linear Ones
• Approximating a class of combinatorial problems with rational objective function
• Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
• Capacitated assortment and price optimization for customers with disjoint consideration sets

This page was built for publication: Approximation algorithms for combinatorial fractional programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4726063)