The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
46 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 ...
0
votes
0answers
125 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 ...
3
votes
0answers
47 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 ...
6
votes
1answer
87 views

Minimize makespan on identical machines when jobs are vectors

Given are $n$ $d$-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 ...
3
votes
2answers
236 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 ...
0
votes
0answers
37 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 ...
5
votes
1answer
115 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. ...
3
votes
0answers
101 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 = ...
3
votes
1answer
442 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 ...
3
votes
1answer
105 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: ...
3
votes
1answer
182 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 ...
4
votes
0answers
437 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 ...
7
votes
1answer
196 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$, ...
2
votes
0answers
190 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 ...
14
votes
0answers
274 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)$ ...
9
votes
1answer
298 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 ...
23
votes
3answers
677 views

Convex Body with minimum expected l2 norm

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 ...
2
votes
0answers
133 views

how to cover a set in a grid with as few rectangles as possible [closed]

In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close ...
6
votes
1answer
816 views

Universal Function approximation

It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function. What other ...