The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum $b$-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the $k$-degenerate graphs, whose approximation ratios are $\alpha +2k -2$ and $\alpha k$, where $\alpha$ is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an $(\alpha + k)$-approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are $k$-systems with independence oracles.


翻译:图形上定义的独立系统最大化是组合优化问题的一般化, 如最大值对齐、 未加权的 MAX- SAT、 配对类和最大时间匹配问题。 在本文中, 我们考虑本地孔雀模型下的问题, 通过使用本地接近度来调查问题的全球近似性。 我们首先分析两种简单的算法: 固定值和贪婪, 以便在模型下最大化, 这表明它们没有恒定的近似率 。 这里的固定值和贪婪算法分别应用固定和贪婪的脊椎定序的本地孔雀。 我们然后为美元- 脱基因图案提出两种近似算法, 其近似率为 $+2k-2 和 $ alpha k 。 $\ alpha 是本地孔雀斑的近似率率。 第二种算法可以普遍化为高度设置 。 我们还提议用 $ (alpha+ k) 美元- appregrocifical 算s 系统, 其独立度为双部的当地标准。

0
下载
关闭预览

相关内容

【2022新书】谱图理论,Spectral Graph Theory,100页pdf
专知会员服务
74+阅读 · 2022年4月15日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
39+阅读 · 2020年9月6日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
NeuralPS'20 | Graph Meta Learning via Local Subgraphs
图与推荐
3+阅读 · 2021年10月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年10月5日
Arxiv
0+阅读 · 2022年10月2日
Arxiv
0+阅读 · 2022年10月2日
Arxiv
0+阅读 · 2022年9月30日
Arxiv
12+阅读 · 2021年3月24日
VIP会员
相关VIP内容
【2022新书】谱图理论,Spectral Graph Theory,100页pdf
专知会员服务
74+阅读 · 2022年4月15日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
39+阅读 · 2020年9月6日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
NeuralPS'20 | Graph Meta Learning via Local Subgraphs
图与推荐
3+阅读 · 2021年10月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员