wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

approximation (930B)

      1 # Approximation
      2 
      3 Two kinds of approximation:
      4 - [approximation_additive]: section 3.2.1 [souihli2012querying] [monte_carlo] [hoeffdings_inequality]
      5 - [approximation_multiplicative]: what follows is about those
      6 
      7 Complexity classes [approximation_class]:
      8 - [FPRAS]
      9 - [PRAS]
     10 - etc.
     11 
     12 Problems: [approximation_problems]
     13 
     14 Reasons not to get it:
     15 - conditional inapproximability [fpras_vs_npc]: no FPRAS if the [decision_problem] "décision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp]
     16 - [sharp_is]: no FPRAS to count the [independent_set] of a [graph]
     17 - no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras]
     18 - [hardness_of_approximation]
     19 
     20 Applications:
     21 - [sampling_approximate]
     22 - [counting_approximate]
     23 
     24 - [approximation_pqe]
     25 
     26 Notion of [reduction]: [approximation_preserving_reduction]
     27 
     28 Other notion: [query_approximation]
     29 
     30 Up: [research_directions]
     31 
     32 Aliases: approximate counting