wiki_research

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

approximation (1069B)

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