On the tightness of an LP relaxation for rational optimization and its applications

DOI10.1016/J.ORL.2016.07.001MaRDI QIDQ1755822zbMATH OpenOpenAlexFDO

Authors Vashist Avadhanula, Jalaj Bhandari, Vineet Goyal, Assaf Zeevi

Publication date 11 January 2019

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2016.07.001

zbMATH Keywords

assortment optimizationlinear programmingPTAS

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Combinatorial optimization (90C27) Fractional programming (90C32)

Recommendations

• A PTAS for capacitated sum-of-ratios optimization
• Tractable approximations for assortment planning with product costs
• Approximating Rational Objectives Is as Easy as Approximating Linear Ones
• Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments
• Constrained assortment optimization under the paired combinatorial logit model

Cites work

• An FPTAS for optimizing a class of low-rank functions over a polytope
• Approximating a class of combinatorial problems with rational objective function
• Approximation algorithms for combinatorial fractional programming problems
• Combinatorial Optimization with Rational Objective Functions

Cited in

(5)

• Fractional 0-1 programming: applications and algorithms
• Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0-1 optimization problems with linear constraints
• scientific article; zbMATH DE number 27284 (Why is no real title available?)
• MNL-bandit: a dynamic learning approach to assortment selection
• Constrained multi‐location assortment optimization under the multinomial logit model

This page was built for publication: On the tightness of an LP relaxation for rational optimization and its applications

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