approximation-algorithms

  1. Stacks serving interval storage requests

  2. Unbalanced connected partition

  3. Proof assistant usage in complexity theory research?
  4. Geometric max cover

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

  6. Common terminology used for lower/upper bounds
  7. On approximating problems in $\#P$

  8. An optimal subspace projection problem
  9. Find an approximate argmax using only approximate max queries

  10. \alpha-path on Euclidean graphs
  11. Relation between the integrality gap of primal LP and dual LP
  12. Lower bound for Yao's algorithm on general addition chains?

  13. Hausdorff Distance and Convex Hull
  14. On the impossibility of representing/approximating subadditive function using additive functions

  15. Practical/heuristic algorithm for multi set-cover

  16. Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

  17. Stochastic dynamic programming problem that is Approximation-hard

  18. Clique cover problem

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

  20. Rules of thumb for universal approximation

  21. Why is HyperLogLog (near-)optimal?
  22. hardness of constant approximation of largest matching set

  23. Approximating the Radius of a (Dense) Graph

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

  25. Sparse-cut approximation for well connected graphs

  26. Studying the hardness of polynomial-time approximability using the concept of stability of approximation

  27. Deterministic approximation algorithms for treewidth
  28. Alternative Set Cover Algorithm With Doubling

  29. Coreset and VC dimension

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

  31. Sparse coding and matching pursuit algorithms
  32. Is it sufficient to only check on the vertices? Greedy algorithm

  33. What is known about data structures for encoding a set while considering approximate Rank queries?

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

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

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

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

  38. Finding minimum weight $k$ cliques in a complete graph
  39. Compression algorithms for low-complexity strings?
  40. Approaches for Theoretical Analysis of Estimates of Probability Distributions

  41. Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

  42. What does "no integrality gap" imply?

  43. The importance of Integrality Gap
  44. Is there an approximation algorithm for MAX k DOUBLE SET COVER?

  45. Maximize the weight of MST + sum of vertex weights
  46. Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
  47. Positive cut algorithm on bipartite graphs with negative weights

  48. Max-cut with negative weight edges
  49. Truthful posted-price mechanism with optimal efficiency (social welfare)

  50. Brute force search algorithm for semidefinite programming (representation of spectrahedron)
  51. Set cover problem with the same amount of sets and elements
  52. Maximize number of edges covered by an independent set of vertices

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

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

  55. Approximating the VM packing problem

  56. Quantum complexity of maximum inner product search

  57. Density of multiples

  58. Online/approximate weighted and capacitated bipartite matching

  59. Ordering of a DAG minimizing some definition of cost
  60. Given oracle for Max-3SAT compute clauses that cannot be satisfied
  61. Solution/Hardness of the following (integer) budgeted problem?
  62. algorithms for a large submatrix / general factor / quasi-biclique problem?

  63. Efficient algorithms for counting $k$-clique subgraphs
  64. Partial cover approximation

  65. How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?
  66. Weighted $l_1$ distance

  67. Percolation probabilities

  68. Max-sum graph-partition for maximizing intra-edge weights?

  69. Fast Approximation Algorithms for Covering Design

  70. About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
  71. Quantum approximation algorithms

  72. Does k-PATH admit a constant approximation?

  73. Maximizing a monotone supermodular function s.t. cardinality

  74. Stochastic optimization with erroneous oracles

  75. Maximizing the number of selected edges with opposing requirements

  76. L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

  77. Complexity of minimizing monotone arithmetical formulas

  78. Complexity of approximating the range of a matrix

  79. What is the reverse of greedy algorithm for setcover?
  80. Set Cover variant- improvement over log(n) approximation?

  81. Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

  82. Approximation algorithms for the maximum $2$-independence set problem
  83. maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

  84. Optimal greedy algorithms for NP-hard problems

  85. Approximating the clique size of the graph
  86. Distributing bags of apples equally

  87. Linear Programing with Rounding for the Fire Station Problem

  88. The complexity of decomposing a bi-stochastic matrix

  89. On approx-preserving P- and A-reducibilities

  90. Maximize number of bins and minimize cost of elements chosen from a set

  91. Approximations for the Stable Fixtures Problem

  92. Statistical Algorithms vs Convex Relaxations - Planted Clique

  93. Constrained version of vertex cover in a bipartite graph
  94. The complexity of finding a Borsuk-Ulam point
  95. Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

  96. Which matrix of Q values is being used here?

  97. Approximate matching in table of integer vectors

  98. Is there any exsiting research on this kind of "sorting with constraint" problem?
  99. "conservative approximate Set Cover"?

  100. What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?