Questions about algorithms that solve problems up to some bounded error.

learn more… | top users | synonyms (1)

0
votes
0answers
12 views

How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin separately?

I have these two problems: Problem 1 (Dual bin packing problem) Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$. Question: Find ...
0
votes
1answer
23 views

Finding top k which are the most different from each other

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are. I want to ...
-1
votes
0answers
13 views

3D volume [Volume of a polyhedra in stl form] [on hold]

I will like to calculate the volume of a 3d with Matlab(am new to matlab) in form of an stl. An example we could use to try can be downloaded by clicking here. I tried the steps I saw on mathworks and ...
1
vote
1answer
30 views

Greedy algorithm for submodular optimzation

In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to ...
3
votes
0answers
12 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
1
vote
3answers
61 views

Travelling salesman very rough min and max estimates

Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the ...
3
votes
0answers
29 views

Using Jaro-Winkler similarity to recognize matching strings

How do I use the Jaro-Winkler similarity measure to test whether two strings should be considered to match each other? I tried comparing the Jaro-Winkler score to a fixed threshold: e.g., if the ...
1
vote
0answers
20 views

Dual Signed Kahan Summation

NOTE: This is for a project I'm working on for fun, NOT production code. So I'm working on a pet project that involves reading data in from a sensor and summing it up. The values are mostly ...
0
votes
1answer
40 views

Showing that an algorithm is 2-approximation

I'm having trouble showing that this algorithm is 2-approx. We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the ...
0
votes
1answer
76 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = ...
0
votes
0answers
31 views

Is there a non-linear version of ICA?

"Independent Component Analysis" is this : someone is sampling a random vector $s \in \mathbb{R}^d$ such that all its components $s_i$ are mutually independent and $\mathbb{E}[s_i^4] < 3$ and the ...
1
vote
1answer
23 views

Why is OPT at least the most valuable item for FPTAS Knapsack?

In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V ...
0
votes
0answers
38 views

Relation between Parameterized complexity and Approximation Algorithms

I want to know whether there is a relation between parameterized algorithms and approximation algorithms. Like there will exist a fpt problem for problem P iff it have some f-approx algorithm. I ...
1
vote
1answer
21 views

Is this a kind of “sketching”?

Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ...
2
votes
1answer
29 views

Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

I read it in not only one place. People write theorems of the form: Theorem: ALG is an O(1)-approximation algorithm It means that ALG is a constant factor approximation algorithm but is it safe ...
0
votes
0answers
32 views

How to design an approximation algorithm using another one as a subroutine for this knapsack-like problems?

I have two knapsack-like problems that I would like to compare their optimal values. In the first problem, I have a perfect bipartite graph of size $n$ (a set of edges ...
1
vote
1answer
20 views

How to give an upper bound on this bin packing problem?

In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set ...
4
votes
1answer
39 views

How to give an approximation algorithm for this unusual bin packing problem?

The usual bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & ...
6
votes
1answer
45 views

Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part

I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a ...
3
votes
1answer
29 views

How to correctly define the ratio of an approximation algorithm?

For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal ...
2
votes
1answer
35 views

Solution to a Np-hard problem and its relevance to a dual LP

From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual): Let $y^*$ be ...
6
votes
1answer
143 views

What is the approximation ratio of this randomized algorithm for finding matchings?

I would like to analyze the following algorithm in terms of its approximation ratio. Here is the algorithm: ...
1
vote
1answer
47 views

A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running ...
1
vote
0answers
11 views

Symmetric Roles of the two problem solutions in RINS

Currently, I am reading the paper "Exploring relaxation induced neighborhood to improve MIP solutions" by Danna et.al. from 2004 and they are talking about a symmetric role of incumbent and the ...
3
votes
1answer
28 views

Approximation Algorithm for Independet Set Problem: Any Explanation Please?

I am reading this note on approximation algorithms for independet set problem. I am confused of Theorem 1. and Corollary 3. Here is the statement of Theorem 1. Theorem 1 (Hastad [1]) Unless P = NP ...
1
vote
1answer
81 views

Prize collecting Steiner tree on graph without weights on edges

I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is ...
1
vote
1answer
38 views

About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have, $SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$ where we mean, $SDP(G)$ = The maximum value that the SDP finds of the objective ...
4
votes
0answers
86 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
1
vote
1answer
33 views

Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if ...
3
votes
1answer
27 views

Approximation for vector bin packing

I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing. To clarify, inputs to the bin packing problem ...
4
votes
1answer
44 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
1
vote
0answers
19 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil ...
2
votes
1answer
35 views

Methods for proving upper bound on a-approximiation algorithms? [closed]

I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance. For example, there's a simple randomized algorithm for the ...
1
vote
0answers
24 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $Η$ is the current graph, until there are no more cycles left.What ...
5
votes
1answer
298 views
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
1
vote
1answer
54 views

How Splitting Summation method works

I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and ...
0
votes
0answers
24 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...
5
votes
1answer
174 views

Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant ...
3
votes
1answer
44 views

What is the sqrt(n)-approximation algorithm for set packing problem

The set packing problem is : Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of ...
2
votes
2answers
44 views

Hardness of approximation: what decision problem is hard exactly?

Just a question for personal comprehension. Consider the following statement: It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$. ...
0
votes
1answer
36 views

How does Hassin's algorithm for the Restricted Shortest Path work?

I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds ...
3
votes
1answer
85 views

Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ ...
3
votes
2answers
103 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is ...
2
votes
1answer
91 views

Approximate Subset Sum with negative numbers

I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states: If all numbers are ...
6
votes
2answers
109 views

Why does this graph show the tightness of MST heuristic's 2-approximation bound?

This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a ...
1
vote
1answer
17 views

Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and ...
0
votes
1answer
72 views

Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum $k$-cut problem asks for a minimum weight $k$-cut. For $k=2$ this problem is P. Vazirani in ...
2
votes
1answer
30 views

Converting maximization to minimization in aproximation algorithms

Suppose algorithm A is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm. As you know it is enough to show Sol >= 1/2 OPT What I need to know is, ...
0
votes
0answers
45 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a ...