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

learn more… | top users | synonyms (1)

0
votes
1answer
34 views

What are some approaches to solve these classes of problems efficiently

Good day, Please consider the following problem: 3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge. Each person has a particular numerical preference ...
3
votes
1answer
107 views

Meaning behind 1/ϵ in FPTAS

I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS. A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme ...
-1
votes
0answers
13 views

Give a greedy algorithm(derandomized) for the Maximum directed cut problem achieving an approximation guarantee of factor 1/4 [duplicate]

Maximum directed cut: Given a directed graph G=(V,E) with nonnegative edge costs, find a subset S⊆V to maximize the total cost of edges out of S: cost({(u→v)∣u∈S and v∈S¯}).
3
votes
0answers
26 views

How approximable is time-bounded Kolmogorov Complexity?

Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language ...
1
vote
1answer
20 views

Good resources for understanding semidefinite relaxation for combinatorial problems

I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as ...
2
votes
0answers
23 views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called ...
0
votes
0answers
18 views

Is this algorithm an approximation algorithm?

Let us say that we have a maximization problem $P(n)$ that is NP-hard, where $n$ is the input size. We have found a polytime algorithm that finds a solution $SOL$ to $P(n)$ that is bounded as follows: ...
0
votes
1answer
30 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
vote
1answer
31 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 ...
4
votes
0answers
21 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
65 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
44 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
22 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
78 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
41 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
24 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 ($w_1,...
2
votes
1answer
31 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 $\{(\ell_1,\ell_1),(\ell_2,\...
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 $\{1,\ldots,...
4
votes
1answer
40 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
48 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
31 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
37 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
145 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
58 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
82 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
43 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
92 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
42 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
29 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
46 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 \ell(vw)...
2
votes
1answer
38 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
26 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
497 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
55 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
179 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
45 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
41 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
94 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
115 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 $(\ln n+...