approximation-algorithms

  1. Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

  2. Minimizing SubModular Function: Cardinality

  3. More efficient max-flow algorithms

  4. About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective
  5. What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?

  6. Hardness of Approximation for minimum path cover in an undirected graph?

  7. Getting to local/global minima with (stochastic) gradient descent on non-convex objectives

  8. Approximating a monotone submodular function using a concrete coverage function
  9. Monotone supermodular function minimization under partition matroid constraints

  10. Learning hidden variable distribution

  11. APX-Hard vs NP-Hard
  12. Stacks serving interval storage requests
  13. Unbalanced connected partition
  14. Proof assistant usage in complexity theory research?
  15. Geometric max cover

  16. Does the following problem have a classical name (e.g. max flow, stable matching, etc) and if so is there an efficient solution?

  17. Common terminology used for lower/upper bounds

  18. On approximating problems in $\#P$
  19. An optimal subspace projection problem

  20. Find an approximate argmax using only approximate max queries

  21. \alpha-path on Euclidean graphs

  22. Lower bound for Yao's algorithm on general addition chains?

  23. Hausdorff Distance and Convex Hull
  24. On the impossibility of representing/approximating subadditive function using additive functions
  25. Practical/heuristic algorithm for multi set-cover

  26. Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
  27. Stochastic dynamic programming problem that is Approximation-hard

  28. Clique cover problem

  29. Approximating max degree $3$ perfect matching count?

  30. Rules of thumb for universal approximation
  31. Why is HyperLogLog (near-)optimal?

  32. hardness of constant approximation of largest matching set
  33. Approximating the Radius of a (Dense) Graph

  34. How to partition a graph while minimizing the count of intra-edges?

  35. Sparse-cut approximation for well connected graphs
  36. Studying the hardness of polynomial-time approximability using the concept of stability of approximation

  37. Deterministic approximation algorithms for treewidth
  38. Alternative Set Cover Algorithm With Doubling

  39. Coreset and VC dimension

  40. Looking for approximation class between NPO and Exp-APX

  41. Sparse coding and matching pursuit algorithms

  42. Is it sufficient to only check on the vertices? Greedy algorithm
  43. What is known about data structures for encoding a set while considering approximate Rank queries?

  44. Is the current best approximation ratio for Vertex Cover problem also a lower bound?

  45. Any fast algorithm for minimum cost feedback arc set problem?

  46. Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

  47. On permanent of $\{\pm1,0\}$ matrices

  48. Finding minimum weight $k$ cliques in a complete graph
  49. Compression algorithms for low-complexity strings?

  50. Approaches for Theoretical Analysis of Estimates of Probability Distributions
  51. Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

  52. What does "no integrality gap" imply?

  53. The importance of Integrality Gap

  54. Is there an approximation algorithm for MAX k DOUBLE SET COVER?

  55. Maximize the weight of MST + sum of vertex weights

  56. Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
  57. Positive cut algorithm on bipartite graphs with negative weights
  58. Max-cut with negative weight edges

  59. Truthful posted-price mechanism with optimal efficiency (social welfare)
  60. Brute force search algorithm for semidefinite programming (representation of spectrahedron)

  61. Set cover problem with the same amount of sets and elements

  62. Maximize number of edges covered by an independent set of vertices

  63. Algorithms to approximate a Riemann integrable function by a piecewise constant function

  64. Finding smallest context free grammar that generates a set of sets

  65. Approximating the VM packing problem

  66. Quantum complexity of maximum inner product search
  67. Density of multiples
  68. Online/approximate weighted and capacitated bipartite matching

  69. Ordering of a DAG minimizing some definition of cost
  70. Given oracle for Max-3SAT compute clauses that cannot be satisfied
  71. Solution/Hardness of the following (integer) budgeted problem?

  72. algorithms for a large submatrix / general factor / quasi-biclique problem?

  73. Efficient algorithms for counting $k$-clique subgraphs

  74. Partial cover approximation
  75. How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

  76. Weighted $l_1$ distance
  77. Percolation probabilities

  78. Max-sum graph-partition for maximizing intra-edge weights?
  79. Fast Approximation Algorithms for Covering Design
  80. About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

  81. Quantum approximation algorithms

  82. Does k-PATH admit a constant approximation?

  83. Maximizing a monotone supermodular function s.t. cardinality
  84. Stochastic optimization with erroneous oracles
  85. Maximizing the number of selected edges with opposing requirements

  86. L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph
  87. Complexity of minimizing monotone arithmetical formulas

  88. Complexity of approximating the range of a matrix

  89. What is the reverse of greedy algorithm for setcover?

  90. Set Cover variant- improvement over log(n) approximation?

  91. Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
  92. Approximation algorithms for the maximum $2$-independence set problem

  93. maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

  94. Optimal greedy algorithms for NP-hard problems
  95. Approximating the clique size of the graph
  96. Distributing bags of apples equally
  97. Linear Programing with Rounding for the Fire Station Problem
  98. The complexity of decomposing a bi-stochastic matrix
  99. On approx-preserving P- and A-reducibilities
  100. Maximize number of bins and minimize cost of elements chosen from a set