Combinatorial optimization with rational objective functions

DOI10.1145/800133.804326MaRDI QIDQ5402535zbMATH OpenOpenAlexFDO

Authors Nimrod Megiddo

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804326

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• The complexity of minimum ratio spanning tree problems
• Approximating a class of combinatorial problems with rational objective function
• Approximating Rational Objectives Is as Easy as Approximating Linear Ones
• Ratio combinatorial programs
• Minimum spanning trees with sums of ratios.

Cited in

(12)

• Algorithms and complexity for the almost equal maximum flow problem
• Rational solutions of the graphsack problem
• A minimum concave-cost dynamic network flow problem with an application to lot-sizing
• Approximating a class of combinatorial problems with rational objective function
• Optimal Embedding into Star Metrics
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
• A bicriteria almost equal minimum cost flow model for day-ahead trading
• Vyacheslav Tanaev: contributions to scheduling and related areas
• The complexity of minimum ratio spanning tree problems
• An exact method for assortment optimization under the nested logit model
• Algorithms for Flows over Time with Scheduling Costs
• Approximating Rational Objectives Is as Easy as Approximating Linear Ones

This page was built for publication: Combinatorial optimization with rational objective functions

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