Approximation algorithms for combinatorial fractional programming problems

DOI10.1007/BF02591737zbMATH Open0616.90078OpenAlexW2054058796MaRDI QIDQ4726063FDOQ4726063

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

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

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)

Cites Work

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

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
• Approximation algorithms for feasible cut and multicut problems
• Ratio combinatorial programs
• 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)