Questions about approximation algorithms.
2
votes
0answers
11 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
52 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
62 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 ...
4
votes
2answers
134 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 ...
9
votes
0answers
127 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
42 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 ...
2
votes
1answer
76 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 ...
1
vote
2answers
215 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
57 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 ...
1
vote
0answers
126 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( ...
0
votes
0answers
96 views
proving $P \subseteq PCP(0,O(log(n))$ [closed]
I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to ...
5
votes
1answer
132 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., ...
0
votes
0answers
31 views
Extended Boolean Model explanation? [migrated]
We are implementing extended boolean model, but we cannot figure out how to use the formula given: http://en.wikipedia.org/wiki/Extended_Boolean_model
The formula here: http://cl.ly/image/0f0A0Q2b1f28 ...
5
votes
0answers
79 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}
...
2
votes
0answers
57 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.
...
1
vote
0answers
101 views
What does “no integrality gap” implies?
I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
0
votes
1answer
113 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 ...
4
votes
0answers
99 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 ...
0
votes
1answer
212 views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem.
Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
7
votes
1answer
132 views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.
...
2
votes
0answers
61 views
Small area containing large amount of patterns
The problem:
I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
6
votes
1answer
148 views
Finding appropriate spanning tree of connected bipartite graph
I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?
Problem: We have a connected ...
0
votes
0answers
111 views
Finding minimum weight $k$ cliques in a complete graph
For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar ...
13
votes
1answer
287 views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a ...
5
votes
1answer
161 views
Finding the perfomance ratio in a multicommodity-flow
I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are ...
6
votes
1answer
174 views
Super-polynomial time approximation algorithms for optimization problems
This is motivated by my previous question, Super-polynomial time approximation algorithms for MAX-3SAT.
For many optimization problems, for each one we have inapproximability lower bound $\alpha$ ...
2
votes
0answers
68 views
Benchmarks for approximation algorithms
I'm working on a Haskell library for approximation algorithms. In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others. Of course, I'd like to benchmark my library ...
4
votes
1answer
250 views
LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?
Given any Integer Linear Program (ILP) there are 2 ways to approximate it:
Write down ILP, convert to LP by relaxing the integer constraints and round the solution
Write down the ILP, convert to LP ...
3
votes
1answer
106 views
What is this matrix column-selection problem, and how hard is it to approximate?
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place ...
2
votes
1answer
119 views
How to approximate minimum clique edge cover
I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).
It's clear that actually finding the minimum solution is ...
5
votes
0answers
131 views
K-Clustering of a Graph maximizing intra-cluster weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A complete graph G with ...
3
votes
1answer
213 views
Is there any work on purely functional approximation algorithms?
It seems to me that approximating a solution to an NP-hard problem would be especially hard for the functional programmer. For example, graph problems are commonly NP-hard. But graphs are ...
3
votes
1answer
73 views
Is there an algorithm that's “like” cross-validation for approximation algorithms of NP-hard problems?
I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is. Is there a similar method for ...
7
votes
3answers
265 views
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + ...
0
votes
1answer
221 views
Near-Sort quicksort algorithm faster than O(nlgn) [closed]
Here, we define a nearly-sorted array with k-sized error, as this:
Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices.
For example:
1, 2, 3, 6, ...
7
votes
0answers
122 views
Minimum weight expander
Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
2
votes
1answer
105 views
How can I reduce this kind of BinPack algorithm? (“MinBreak-BinFill”)
I have a special variant of BinPack problem.
Does anyone know how to reduce this problem to something known?
The problem:
There are items $I$ and bins $B$ in specific quantity and size.
$|I| ∈ ℕ, ...
15
votes
4answers
351 views
Approximation algorithms for Maximum Independent Set on special classes of graphs
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better ...
4
votes
1answer
246 views
Path coloring in general graphs
Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.
We know that coloring a set of paths ...
0
votes
0answers
68 views
Partitioning based on distribution
Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution.
For two bins and uniform distribution, this problem is ...
2
votes
0answers
154 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 ...
4
votes
0answers
128 views
Approximation ratio for covering n points in d dimensions
What is best known approximation ratio for the following problem :
Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a ...
21
votes
1answer
337 views
Approximate 1d TSP with linear comparisons?
The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way ...
5
votes
0answers
137 views
Maximizing difference of a submodular and a modular function
I'm considering a network planning problem which is stated as follows:
From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that
\begin{equation}
f(\mathcal{A}) - ...
0
votes
2answers
266 views
Bin packing approximation with different bin sizes
Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?
More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ ...
0
votes
0answers
129 views
Is there an algorithm for finding the maximal edge weight over all spanning trees?
Let $G = (V,E)$ with a weight function $w(e)$ for $e \in E$.
Let $T$ be the set of minimal spanning trees of $G$.
I am interested in finding $\min_{t \in T} \max_{e \in t} w(e)$, where $t$ ranges ...
3
votes
1answer
290 views
Maximizing a convex function with linear constraints
I have the following optimization problem:
$$
\arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\}
\mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq ...
6
votes
2answers
217 views
Vertex subset of maximum size
I was wondering if this problem has a name and/or it has been already studied.
Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ :
Does ...
3
votes
3answers
212 views
bin packing with overlapping objects
I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object ...
3
votes
0answers
102 views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval ...
