Independent Set, Induced Matching, and Pricing: Connections and Tight ... - todo314 @ ウィキ

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses

• Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
• In FOCS

• k-hypergraph Pricing Problem
  • 入力
  • V: 商品
  • E_i: 客iの好きなvのset
    • |E_i|≦k
  • b_i: 客iの予算
  • 出力
  • p_j: v_jの値段
  • 目的
  • max g=Σ_i g_i
  • g_i = \min_{j∈E_i} p_j (p_j≦b_i)
    • つまり一番安いのを買おうとする（無ければ買わない
  • 一番安いのを買うとして、買われた値段の和を最大化
• 流れ？
  • 3-SAT
  • Max-CSP
  • independent set
  • induced matching
  • k-hypergraph pricing
  • ETHの元で、上界と下界をよりタイトにした
• Max-CSPとindependent set
  • FGLSS Graphってのを考える
• 何が新しいの？
  • 組み合わせ？らしい

FOCS

2013-11-03 02:51:01 (Sun)