What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [approximation]

The tag has no usage guidance.

51 questions
Filter by
Sorted by
Tagged with
53 views

### polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
335 views

### Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
80 views

### Optimization problems with same optimal value, but different approximation behavior

Context: related to this answer. I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense ...
257 views

### If NP in BPP then NP equals RP

I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links: https://cs.stackexchange.com/q/80509 http://www.inf.ed.ac.uk/teaching/...
952 views

### Is an algorithm with an approximation factor of 4000 useful?

A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds. To my surprise, when reading the ...
218 views

### Martingale exit arguments for gradient Langevin dynamics

I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
71 views

589 views

### Approximately counting paths and cycles in a graph

Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. The question is about the approximability of these graph ...
100 views

### Does the NP-hardness of finding any valid solution imply NPO-hardness?

Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
168 views

### Universal approximation theorem of second order

The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem) informally states that up to several conditions, any function can be approximated by a shallow ...
475 views

### Why isn't the Charikar algorithm for finding the densest subgraph optimal?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different ...
124 views

### Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i?$" for some $i$, taking the left branch means "yes", ...
352 views

### Is there any known Poly-APX-complete minimimization problem?

All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
190 views

### Proof of a (simple) lemma by Aaronson

I am reading this article, and I need help with an apparently obvious proof. The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real ...
153 views

103 views

196 views

### Is there any research on approximation of reals with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
104 views

### Computing log of sum of positive integers

As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
115 views

### The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
160 views

### Finding optimal subset for quadratic function

Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of ...
45 views

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\... 0answers 81 views ### How can I show that zero-one programming is not in APX? How can I show that zero-one programming is not in APX? Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the zero-one programming problem to Vertex Cover and show that ... 0answers 207 views ### Calculating exact/approximate solution to a formula Suppose we have a set of variable$\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions$g_i(y_i), 1 \leq i \leq n$. Note that$g_i()$is dependent only on$y_i$. Consider ... 0answers 61 views ### Do there exist “odd times” cover problems and what do we know about their approximability? I am currently investigating a problem which can be formulated as a cover problem, in which real intervals have to be covered an odd number of times by integers. My question is just, if anybody has ... 1answer 177 views ### Minimize makespan on identical machines when jobs are vectors Given are$nd$-dimensional vectors and$m$machines where$d$need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the ... 2answers 995 views ### Greedy MAX SAT approximation ratio Consider a naive MAX SAT approximation algorithm: pick a literal$l$which appears in maximum number of clauses set the corresponding variable of$l$, such that all clauses containing$l$are ... 0answers 59 views ### Asymmetric metric TSP when many edges have equal costs in both directions I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for$O(log(|E|)$edges, or something close/related to ... 1answer 754 views ### Approximating Max-Coverage when the elements need to be covered multiple times In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. ... 1answer 804 views ### Max-cut equivalence with most likely assignment to an Ising model Ising Model $$Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)$$ In which$\lambda_{ij} \in \mathbb{R}$, and $$x_{ij} = \begin{cases} 1 & x_i = ... 1answer 905 views ### Finding maximum number of disjoint set covers Let U = [1..n] be the universe of n elements and C be a collection of subsets of U, C= S_1, \dots, S_m, where S_i \subset U. Then the problem is to find as many partitions of C, such ... 1answer 159 views ### n-approximable functions I came across the following definition in a paper: We can extend the notion of an n-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: ... 1answer 278 views ### Approximating Bipartite Vertex Cover Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover ... 0answers 848 views ### k-CNF ←→ k-DNF conversion to minimize errors the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ... 1answer 310 views ### Understanding bounded-diameter decomposition of graphs for PTAS While trying to understand Baker's approach (also explained in this article by Eppstein) to designing PTAS's for planar graphs, I came across a difficulty. The idea is, given an integer k, ... 0answers 266 views ### Maximizing a convex function where the objective function is separable but the search space is not The problem statement is Given convex functions f_i over X, find$$\arg\max_{x\in X} \sum_i f_i(x)$$Does this kind of problem structure allow one to use specific strategies to solve the ... 0answers 349 views ### Finding all-pairs anti-distance Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem. Let$G=(V,E)$... 1answer 436 views ### Algorithm for approximating convex bodies by a convex hull of ellipsoids I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body$K$by the convex hull of$...
Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...