Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

5
votes
1answer
278 views

Worst case ratio between minimum clique cover and maximum independent set

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
1
vote
0answers
62 views

Sync time between two points

Suppose we have two points, A and B, each point has its own clock. We are able to send messages between ...
4
votes
0answers
488 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just $\...
1
vote
0answers
211 views

Generalization Issues with Practical Suggestions from Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof of the Universal Approximation Theorem for Neural Networks, I wonder: if we use a piecewise ...
4
votes
0answers
82 views

Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
6
votes
2answers
686 views

Edge and vertex fault tolerance in graphs

Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What ...
5
votes
2answers
590 views

Variants of Densest Subgraph Problems

Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$: (1) Average degree of vertices in $H$ (2) What I will ...
3
votes
1answer
203 views

Adaptive vs Bernoulli sampling

Flajolet analyzed Wegman's Adaptive Sampling for estimating distinct values (species) in a stream (population), giving an unbiased estimator for mean and specified the standard error to be ...
1
vote
1answer
122 views

Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm

First thing first - I am not a CS guy. I am EE student (Systems and Signals). So it would help if you didn't use any big words :) The Multi-terminal cut the input is a graph G and a subset T of its ...
9
votes
0answers
247 views

Approximating a convex polyhedron, with fewer inequalities

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words, $$\mathcal{...
4
votes
1answer
200 views

Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient ...
6
votes
2answers
6k views

Top-k frequent items in data stream

Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set. I am thinking about ...
2
votes
0answers
120 views

Tiling a rectangle with weighted cells (min-max problem)

Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by ...
15
votes
2answers
308 views

Approximation in subexponental time

There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete ...
4
votes
0answers
177 views

Size of Independent set of sparse graphs with few triangles

Notations $\alpha(G) = $ Max sized independent set of graph $G$. $n(G) = $ Number of vertex in graph $G$. Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$, $$\...
8
votes
0answers
217 views

Complexity and approximability of maximum edge biclique problem on co-comparability graphs

A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph. Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete ...
0
votes
1answer
138 views

Planning jobs as partition problem

I think this should be a famous problem but I could not find its name. I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines. How can I assign jobs to machines to minimize ...
3
votes
1answer
1k views

Steiner tree problem for unweighted graphs

Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number ...
3
votes
1answer
928 views

Approximate Maximum Weight Matching

I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me? In my problem, I have a bipartite graph with N abound 1000 (#vertices on each ...
5
votes
1answer
274 views

Best approximation for a HYPERGRAPH-MAXDICUT problem

Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
5
votes
1answer
178 views

PTAS for a variant of multiple knapsack?

I am interested in the following variant of multiple knapsack. There are $n$ items with values $v_1,\ldots,v_n$. We want to partition the items into $m$ subsets $S_1,\ldots,S_m$ to maximize $\min_{j\...
2
votes
0answers
58 views

Approximating BLEDP on restricted graph classes

In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of ...
3
votes
1answer
127 views

Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following. Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of ...
-3
votes
1answer
98 views

what problem is this? [closed]

I have this instance: Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ...
2
votes
0answers
305 views

The non-metric k-median problem

It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic ...
0
votes
0answers
180 views

Finding assignment-minimum complete k-partite graph cover

Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs? I'm assuming this problem is NP-...
1
vote
2answers
316 views

algorithms to split data into roughly equal sized quantiles

What is the state-of-the art on algorithms that calculate/estimate approximate quantiles? I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having ...
13
votes
1answer
342 views

Good reference about approximate methods for solving logic problems

It is known that many logic problems (e.g. satisfiability problems of several modal logics) are not decidable. There are also many undecidable problems in algorithm theory, e.g. in combinatorial ...
11
votes
1answer
215 views

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

Has this problem been studied before? Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
11
votes
2answers
3k views

Find all pairs of values that are close under Hamming distance

I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid. ...
4
votes
1answer
180 views

Approximating Min-Sum Set Multicover

Approximations for the set multicover problem have been studied (Rajagopalan & Vazirani (section 5)), as have approximations for the min-sum set cover problem (Feige et al.). The greedy heuristic ...
0
votes
1answer
1k views

Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the ...
1
vote
0answers
210 views

A non-trivial combinatorial optimization

So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
2
votes
0answers
96 views

Optimal additive basis for decomposing/partitioning an integer as a sum of two integers

I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$. A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ ...
11
votes
1answer
158 views

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a ...
1
vote
1answer
216 views

number of PCP queries

we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?
3
votes
0answers
277 views

Approximation factor when objective can be negative

In Williamson and Shmoys' textbook The Design of Approximation Algorithms they make the following assumption: We assume that there is some objective function mapping each possible solution of an ...
5
votes
2answers
836 views

Approximation algorithm for finding the maximum common subgraph in two DAGs

Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a ...
12
votes
1answer
430 views

Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
4
votes
0answers
152 views

Find index set partition that has large projections

I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
2
votes
1answer
274 views

Minimum-area orthogonal rectangle coverage

Suppose there are N orthogonal rectangles on the planes, overlapping or not. I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely ...
22
votes
2answers
13k views

Universal Approximation Theorem — Neural Networks

I posted this earlier on MSE, but it was suggested that here may be a better place to ask. Universal approximation theorem states that "the standard multilayer feed-forward network with a single ...
0
votes
1answer
243 views

PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Problem 1 I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time ...
2
votes
0answers
359 views

VC dimension for ellipsoidal classifiers

What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as $$ g( x, (P_1,p_2,p_3), ) := \text{sgn} \left( x^\...
5
votes
1answer
316 views

Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., ...
5
votes
0answers
133 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize the quantity \begin{equation} \sum_{k=...
2
votes
0answers
81 views

General covering approximation

Consider the following integer program (general covering): $\min c \cdot x$ subject to $Ax \ge b$, where all entries in $A, b, c$ are nonnegative and $x$ is required to be nonnegative and integral. ...
4
votes
0answers
261 views

What does “no integrality gap” imply?

I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale ...
0
votes
1answer
389 views

FPTAS for Number Partition Problem

I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of ...
6
votes
0answers
289 views

Bipartite vertex separator

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...