# Tagged Questions

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

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 ...
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 ...
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¯}).
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1answer
78 views

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 ...
1answer
24 views

1answer
20 views

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 ...
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 ...
1answer
497 views

### PTAS definition vs. FPTAS

From what I read in the ...
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 ...
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 ...
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$, ...
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 ...
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 ...
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$. ...
1answer
41 views