Approximation algorithm for a class of global optimization problems

被引:0
作者
Marco Locatelli
机构
[1] Università di Parma,Dipartimento di Ingegneria dell’Informazione
来源
Journal of Global Optimization | 2013年 / 55卷
关键词
Approximation algorithms; Nondecreasing functions; Superhomogeneous functions; Ratio functions;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper we develop and derive the computational cost of an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon}$$\end{document} -approximation algorithm for a class of global optimization problems, where a suitably defined composition of some ratio functions is minimized over a convex set. The result extends a previous one about a class of Linear Fractional/Multiplicative problems.
引用
收藏
页码:13 / 25
页数:12
相关论文
共 50 条
  • [21] Approximation Algorithms for Optimization Problems in Random Power-Law Graphs
    Shen, Yilin
    Li, Xiang
    Thai, My T.
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 : 343 - 355
  • [22] Approximation algorithms for facility location problems with a special class of subadditive cost functions
    Gabor, Adriana E.
    van Ommeren, Jan-Kees C. W.
    THEORETICAL COMPUTER SCIENCE, 2006, 363 (03) : 289 - 300
  • [23] SAMPLING AND COST-SHARING: APPROXIMATION ALGORITHMS FOR STOCHASTIC OPTIMIZATION PROBLEMS
    Gupta, Anupam
    Pal, Martin
    Ravi, R.
    Sinha, Amitabh
    SIAM JOURNAL ON COMPUTING, 2011, 40 (05) : 1361 - 1401
  • [24] Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
    So, Anthony Man-Cho
    MATHEMATICAL PROGRAMMING, 2011, 129 (02) : 357 - 382
  • [25] On greedy approximation algorithms for a class of two-stage stochastic assignment problems
    Karademir, Serdar
    Kong, Nan
    Prokopyev, Oleg A.
    OPTIMIZATION METHODS & SOFTWARE, 2014, 29 (01) : 42 - 67
  • [26] Accelerated Projection Algorithm Based on Smoothing Approximation for Distributed Nonsmooth Optimization
    Zhao, You
    Liao, Xiaofeng
    He, Xing
    IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, 2023, 10 (04): : 1682 - 1694
  • [27] A 2-approximation algorithm for path coloring on a restricted class of trees of rings
    Deng, XT
    Li, GJ
    Zang, WN
    Zhou, Y
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 47 (01): : 1 - 13
  • [28] A Multi-Strategy Seeker Optimization Algorithm for Optimization Constrained Engineering Problems
    Duan, Shaomi
    Luo, Huilong
    Liu, Haipeng
    IEEE ACCESS, 2022, 10 : 7165 - 7195
  • [29] An approximation algorithm for approximation rank
    Lee, Troy
    Shraibman, Adi
    PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, : 351 - +
  • [30] AN APPROXIMATION ALGORITHM FOR SOLVING UNCONSTRAINED 2-DIMENSIONAL KNAPSACK-PROBLEMS
    FAYARD, D
    ZISSIMOPOULOS, V
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 84 (03) : 618 - 632