Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
52 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
user avatar
0 votes
0 answers
20 views

How can I find the largest bipartite graph?

A bipartite graph corresponds to a rectangle of ones in the adjacency matrix of this graph. Having a sparse graph, I would like to find the largest approximated bipartite graph. approximated means ...
user avatar
1 vote
1 answer
39 views

MAX-SAT 2-Approximation algorithm

I have the two following questions: I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation ...
user avatar
  • 37
1 vote
1 answer
30 views

Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio

In the scheduling problem, the input is a sequence $T_1,T_2,...,T_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines. The ...
user avatar
-2 votes
1 answer
47 views

Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)

0 < x,a,b,c,d < M are all positive integers (uint64). also, a<b if that helps. we have assembler (integer only) operations available (e.g. division only yields integers). we want to ...
user avatar
0 votes
0 answers
16 views

Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?

Disjoint Group Steiner Tree (DGST) is the following problem: Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
user avatar
1 vote
1 answer
27 views

Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
user avatar
  • 37
0 votes
0 answers
36 views

Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
user avatar
0 votes
1 answer
63 views

approximation ratio of TSP problem where the weights are bounded by an inequality

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time ...
user avatar
0 votes
1 answer
17 views

Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?

So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if : $A \geq opt(1-\epsilon) \; ,\forall \epsilon > 0$ (and I guess ...
user avatar
1 vote
1 answer
43 views

Can we show that #3CNF is in FPTAS

If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
user avatar
  • 33
1 vote
0 answers
64 views

Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?

If you have an $\alpha$-approximation algorithm $A$ for some problem $f \in \#P$, such that (for $0 < \alpha \leq 1$) $$ \alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha}, $$ does that automatically ...
user avatar
  • 33
1 vote
0 answers
21 views

Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
user avatar
1 vote
0 answers
18 views

Algorithm for modified 2D irregular bin packing

So usually bin packing algorithms compute the tightest packed solution. I want to calculate the opposite, in my case the solution with the most space between the packed objects is needed. I tried ...
user avatar
0 votes
0 answers
22 views

How to proof This for Maximum Independent Set Problem?

Show that the problem of finding a Maximum Independent Set doesn't have approximation with factor $\Omega(\frac{1}{n^{1-\epsilon}})$ unless P = NP.
user avatar
1 vote
1 answer
38 views

Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
user avatar
1 vote
1 answer
70 views

Inapproximability of an optimization problem

Suppose we have an optimization problem $\mathcal{P}$ that we should cover all points with $k$ disjoint rectangles in the plane and we should optimize a distance function over each rectangles . Now, ...
user avatar
  • 1
1 vote
0 answers
23 views

Weighted k-medians problem

Facility location and $k$-medians are closely related problems in CS. We are given a set of facilities (each with a weight), a set of clients to serve where a facility $i$ can serve a client $j$ with ...
user avatar
  • 129
1 vote
1 answer
38 views

Generate degree-bound LFSR to approximate given sequence

Given an output sequence, $S$, we can use the Berlekamp-Massey algorithm to find the shortest LFSR, of order $n \leq |S|$, which exactly generates that sequence. Is it possible to efficiently compute ...
user avatar
  • 123
1 vote
1 answer
39 views

Is there a way to determine the LCS of three based on the LCS-s of all three pairs?

Let $\Sigma$ be an alphabet of some symbols, and let $\mathrm{lcs}$ denote the length of the longest common subsequence of two or more sequences defined on $\Sigma$. For some $A,B,C\in\Sigma^{\star}$, ...
user avatar
  • 111
0 votes
0 answers
11 views

How to evaulate the upper-bound for a multiobjective optimazation problem?

Given a product set $P$, where each product $p_i \in P$ has a cost $p_i.\!c$ and a value $p_i.\!v$. Therefore, $\forall p_i \in P$, $p_i.\!c > 0$ and $p_i.\!v > 0$. The cost-efficiency of a ...
user avatar
  • 1
0 votes
0 answers
66 views

Can this kind of NP-Hard problem be approximated?

Consider this kind of optimization problem: (1) The problem aims to minimize a value. Let n denote this value. (2) To determine whether n = 0 is a NP-Complete problem. It is obvious that this kind of ...
user avatar
  • 69
7 votes
3 answers
2k views

What is the fastest algorithm to approximate an irrational number with specified precision?

Problem Background: Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
user avatar
1 vote
0 answers
22 views

Best known approximation for P2|tree;pj=1;Mj|Cmax

I am looking for the best known approximation algorithm for the scheduling problem $P2|tree;p_j=1;M_j|C_{max}$, which to my knowledge is at least $\mathbb{NP}$-hard. A more elaborate description of ...
user avatar
  • 11
1 vote
1 answer
29 views

Radius Local Search Algortihm for Max-Sat problem approximating ratio

Assume that in classical Local Search algorithm for MAX-SAT we could flip no more than $r \leq n/2$ variables (let's call it $r$-flip) on every iteration. More precise: on every iteration we're ...
user avatar
0 votes
1 answer
38 views

Using an optimal number of agents, maximise coverage of an area while minimising distance travelled

I'm a CS Year 2 student working on a team project which requires a solution to the following problem: Given a starting position on the edge of an irregular shape (example above) and a maximum number ...
user avatar
1 vote
1 answer
48 views

Finding 2 paths between 2 source-target pairs

Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-...
user avatar
1 vote
0 answers
22 views

Proof that there isn't a $c$-additive approximation to Partition Problem

Define Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal. Is there a proof that there isn't an additive approximation ...
user avatar
1 vote
0 answers
86 views

Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
user avatar
  • 111
2 votes
2 answers
100 views

Bin-packing with a capacity constraint on pairs of bins

In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum. ...
user avatar
3 votes
1 answer
58 views

Bisecting Intervals of floating point numbers containing 0 and infinity fairly

It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $[a,b]$ on the real number line ...
user avatar
4 votes
0 answers
39 views

K-means, but normalized and with max

Given points $x_1, \ldots, x_n$ in the Euclidean space and $K \in \mathbb N$, I'm interested in the following objective. Partition the points into $K$ clusters $C_1, \ldots, C_K$ so that: $$\max_{i \...
user avatar
  • 196
5 votes
1 answer
111 views

A dynamic program to decide whether the solution is in a given range

In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. The problem can be ...
user avatar
3 votes
1 answer
146 views

A complexity class between P and FPTAS

The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
user avatar
1 vote
1 answer
40 views

Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?

A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
user avatar
1 vote
0 answers
33 views

Routing in ring network topology

I want to find 2-approximation algorithm for finding path of m messages sent from m computers to m different computers in a ring topology with n nodes. I know about clockwise embedding, which takes ...
user avatar
2 votes
1 answer
58 views

Meaning of "approximation within $n^{1−\epsilon}$"

I am not sure I understand correctly the following assertion (source): For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard. Does this mean that, for any ...
user avatar
  • 291
0 votes
1 answer
30 views

Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
user avatar
  • 398
0 votes
1 answer
41 views

polynomial time approximation algorithm problem

How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem? For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
user avatar
0 votes
0 answers
19 views

How to read the optimal makespan

Hello I'm having trouble reading the optimal makespan of job scheduling algorithm. In particular what does it mean for max to have index i here?
user avatar
0 votes
0 answers
17 views

Need Help Solve an NP problem with an Approximation Algorithm

I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example. Given $n$ objects, each with $k$ possible properties, ...
user avatar
0 votes
0 answers
108 views

Multivariate piecewise linear interpolation

I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm. ...
user avatar
1 vote
0 answers
41 views

Exact and approximate agorithms for independent set probem in large graphs

I have a problem which could be stated as follows: Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
user avatar
1 vote
1 answer
30 views

Embedding from $L^\infty$ space to $L^2$ space

I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ ...
user avatar
  • 196
2 votes
1 answer
78 views

What is an O(n)-approximation?

I see the following notations used: $O(1)$-approximation $O(n)$-approximation $\Omega(n)$-approximation Can someone please explain what they mean? I know what an approximation is with a normal ...
user avatar
0 votes
0 answers
35 views

An approximation algorithm for partitioning metric completed graph

Given complete metric weighted graph $G=(V,E)$ with $n$ vertices. Are there an algorithm that partition $G$ into to disjoint part $(C_1,C_2)$ that sum of heaviest edge $e\in C_1$ and heaviest edge $e'...
user avatar
2 votes
1 answer
115 views

Currently best approximation for graph coloring

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
user avatar
  • 314
0 votes
0 answers
25 views

Is it possible to replace the softmax in the Nyströmformer?

My question is about the article Nyströmformer A Nyström-based Algorithm for Approximating Self-Attention. and also about the $\alpha$-entmax $(\boldsymbol{z})=[(\alpha-1) \boldsymbol{z}-\tau \mathbf{...
user avatar
  • 137
0 votes
2 answers
40 views

Failing to calculate the gradient and y-shift for best fit line using sum-squares method. Can anyone help me to pinpoint the issue?

I'm trying to work out how to make the working implementation of fitting the straight line among the set data points. I base my function: ...
user avatar
1 vote
1 answer
26 views

Textbook proofs for approximation algorithms for scheduling

I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) ...
user avatar

1
2 3 4 5
11