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 条
[41]   APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS [J].
Wang, Lusheng ;
Lin, Yu ;
Liu, Xiaowen .
SIAM JOURNAL ON COMPUTING, 2008, 38 (04) :1504-1518
[42]   A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria [J].
Srinivasan, A ;
Teo, CP .
SIAM JOURNAL ON COMPUTING, 2001, 30 (06) :2051-2068
[43]   An Improved Approximation Algorithm for ATSP [J].
Traub, Vera ;
Vygen, Jens .
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, :1-13
[44]   Approximation Algorithms for the Class Cover Problem [J].
Adam H. Cannon ;
Lenore J. Cowen .
Annals of Mathematics and Artificial Intelligence, 2004, 40 :215-223
[45]   Approximation algorithms for the class cover problem [J].
Cannon, AH ;
Cowen, LJ .
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2004, 40 (3-4) :215-223
[46]   Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT [J].
van Maaren, H ;
Warners, JP .
DISCRETE APPLIED MATHEMATICS, 2000, 107 (1-3) :225-239
[47]   Submodular Functions: Optimization and Approximation [J].
Iwata, Satoru .
PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS, VOL IV: INVITED LECTURES, 2010, :2943-2963
[48]   A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems [J].
Lin, Gui-Hua ;
Yang, Zhen-Ping ;
Yin, Hai-An ;
Zhang, Jin .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2023, 86 (02) :669-710
[49]   Approximation schemes for minimum latency problems [J].
Arora, S ;
Karakostas, G .
SIAM JOURNAL ON COMPUTING, 2003, 32 (05) :1317-1337
[50]   Approximation algorithms for partial covering problems [J].
Gandhi, R ;
Khuller, S ;
Srinivasan, A .
AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING, 2001, 2076 :225-236