An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function

Victor P. Ilev

首页> 外文期刊>Discrete Applied Mathematics >An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function

【24h】

An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function

机译：最小化超模集函数的贪婪下降算法的逼近保证

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We consider the problem of minimizing a supermodular set function whose special case is the well-known NP-hard p-median problem. The main result of the paper is a tight bound on the approximation ratio of a greedy heuristic (discrete analog of the steepest descent algorithm) for this problem.

机译：我们考虑使超模集函数最小化的问题，其特例是众所周知的NP硬p中值问题。本文的主要结果是针对该问题的贪婪启发式算法（最速下降算法的离散模拟）的逼近率的严格边界。

著录项

来源
《Discrete Applied Mathematics》 |2001年第3期|共16页
作者
Victor P. Ilev;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
approximation algorithm; greedy heuristic; supermodular set function;

机译：近似算法贪婪启发式超模集函数;

相似文献

外文文献
中文文献
专利

1. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function [J] . Victor P. Ilev Discrete Applied Mathematics . 2001,第1a3期

机译：最小化超模集函数的贪婪下降算法的逼近保证
2. Greedy Minimization of Weakly Supermodular Set Functions [J] . Edo Liberty, Maxim Sviridenko LIPIcs : Leibniz International Proceedings in Informatics . 2017,第1期

机译：弱超模集函数的贪婪极小化
3. COORDINATE DESCENT OPTIMIZATION FOR l(1) MINIMIZATION WITH APPLICATION TO COMPRESSED SENSING; A GREEDY ALGORITHM [J] . Li YY, Osher S Inverse problems and imaging . 2009,第3期

机译：l（1）最小化的协调下降优化在压缩感测中的应用;贪心算法
4. Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions [C] . Kaito Fujii International Conference on Machine Learning . 2021

机译：近似保证本地搜索算法的定位函数
5. Greedy Algorithms in Approximation Theory and Compressed Sensing. [D] . Yang, Mingrui. 2011

机译：近似理论和压缩感知中的贪婪算法。
6. Data from multimodal functions based on an array of photovoltaic modules and an approximation with artificial neural networks as a scenario for testing optimization algorithms [O] . Carlos Robles-Algarín, Diego Restrepo-Leal, Adalberto Ospino Castro 2019

机译：来自基于光伏模块阵列的多峰函数的数据以及人工神经网络的近似值作为测试优化算法的场景
7. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function [O] . Ilev Victor P. 2001

机译：最小化超模集函数的贪婪下降算法的近似保证

An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function

摘要

著录项

相似文献

相关主题

期刊订阅