咨询与建议

限定检索结果

文献类型

  • 2 篇 期刊文献
  • 1 篇 会议

馆藏范围

  • 3 篇 电子文献
  • 0 种 纸本馆藏

日期分布

学科分类号

  • 3 篇 工学
    • 3 篇 计算机科学与技术...
    • 1 篇 软件工程
  • 1 篇 理学
    • 1 篇 数学

主题

  • 3 篇 sub-exponential ...
  • 2 篇 approximation al...
  • 1 篇 agnostic boostin...
  • 1 篇 hardness of appr...
  • 1 篇 knapsack
  • 1 篇 agnostic learnin...
  • 1 篇 set cover
  • 1 篇 exponential algo...
  • 1 篇 lift-and-project...
  • 1 篇 learning parity ...

机构

  • 1 篇 ryerson univ dep...
  • 1 篇 georgia inst tec...
  • 1 篇 ben gurion univ ...
  • 1 篇 univ paris 09 ps...
  • 1 篇 google inc ny us...
  • 1 篇 middlesex univ d...
  • 1 篇 tsinghua univ in...
  • 1 篇 univ alberta dep...

作者

  • 1 篇 friggstad zachar...
  • 1 篇 chlamtac eden
  • 1 篇 georgiou konstan...
  • 1 篇 mansour yishay
  • 1 篇 kalai adam tauma...
  • 1 篇 paschos vangelis...
  • 1 篇 lampis michael
  • 1 篇 bonnet edouard
  • 1 篇 verbin elad

语言

  • 3 篇 英文
检索条件"主题词=Sub-exponential algorithms"
3 条 记 录,以下是1-10 订阅
排序:
Lift-and-Project Methods for Set Cover and Knapsack
收藏 引用
ALGORITHMICA 2018年 第12期80卷 3920-3942页
作者: Chlamtac, Eden Friggstad, Zachary Georgiou, Konstantinos Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ Alberta Dept Comp Sci Edmonton AB Canada Ryerson Univ Dept Math Toronto ON Canada
We study the applicability of lift-and-project methods to the SET COVER and KNAPSACK problems. Inspired by recent work of Karlin et al. (IPCO 2011), who examined this connection for KNAPSACK, we consider the applicabi... 详细信息
来源: 评论
Time-approximation trade-offs for inapproximable problems
收藏 引用
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 92卷 171-180页
作者: Bonnet, Edouard Lampis, Michael Paschos, Vangelis Th. Middlesex Univ Dept Comp Sci London England Univ Paris 09 PSL Res Univ CNRS UMR 7243LAMSADE F-75016 Paris France
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves is the allowed running time is gradually increased from polynomial to (sub-)exponential. We t... 详细信息
来源: 评论
On Agnostic Boosting and Parity Learning  08
On Agnostic Boosting and Parity Learning
收藏 引用
14th Annual ACM International Symposium on Theory of Computing
作者: Kalai, Adam Tauman Mansour, Yishay Verbin, Elad Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Google Inc New York NY USA Tsinghua Univ Inst Theoret Comp Sci Beijing Peoples R China
The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an arbitrary distribution, we would like to produce ... 详细信息
来源: 评论