# Questions tagged [approximation]

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

549 questions
Filter by
Sorted by
Tagged with
I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is: $$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{... 1 vote 1 answer 146 views ### Job scheduling approximation In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3.... 5 votes 1 answer 363 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 1 answer 64 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 ... 0 votes 1 answer 183 views ### set cover to edge cover I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ... 1 vote 0 answers 63 views ### Estimating column sums of A_1,\ A_1 A_2,\ A_1A_2A_3,\ \ldots Given n\times n dense real valued matrices A_1,\ldots, A_L let P_i=A_1\ldots A_i For each P_i I'm interested in obtaining the sum of all rows, and the sum of all columns. Naive approach: ... 0 votes 1 answer 629 views ### Proving there is no polynomial algorithm for independent set I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ... 3 votes 4 answers 898 views ### Better results for minimum vertex cover algorithms Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results. All the articles I read so far were way too complicated for me,... 0 votes 1 answer 65 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 ... 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 ... 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 ... -2 votes 1 answer 48 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 ... 1 vote 1 answer 35 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 ... 1 vote 1 answer 44 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 ... 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 \... 1 vote 1 answer 28 views ### Max matching algorithm lemma approximation algorithm We have this algorithm which is supposed to find max matchings. ... 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 ... 3 votes 1 answer 2k views ### Run Christofides algorithm by hand with wrong result I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example The graph: Calculate minimum spanning tree T: Calculate the set of vertices O with odd degree in T.... 0 votes 1 answer 41 views ### Polynomial and fully polynomial time approximation scheme How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide? 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 ... 3 votes 1 answer 153 views ### Approximation factor preserving reduction The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let \Pi_1 and \Pi_2 be two minimization problems, an approximation factor preserving ... 6 votes 1 answer 287 views ### Find maximal subgraph containing only nodes of degree 2 and 3 [closed] I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ... 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 ... 3 votes 1 answer 311 views ### smaller size approximation to minimum vertex cover Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ... 0 votes 1 answer 83 views ### On FPTAS and many one parsimonious reductions We have two NP complete problems \Pi_1 and \Pi_2. Suppose \Pi_1\rightarrow\Pi_2 be a many one parsimonious reduction. If \Pi_1 has an FPTAS then does \Pi_2 also have? If \Pi_2 has an ... 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 ... 1 vote 0 answers 19 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 ... 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. 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-... 3 votes 1 answer 59 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 ... 1 vote 1 answer 72 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, ... 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 ... 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: ... 1 vote 1 answer 39 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 ... 1 vote 1 answer 41 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}, ... 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 ... 0 votes 0 answers 67 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 ... 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 ... 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 ... 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 ... 0 votes 1 answer 39 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 ... 1 vote 1 answer 50 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-... 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 ... 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. ... 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 ... 1 vote 0 answers 94 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 ... -1 votes 1 answer 72 views ### acyclic and disjoint union I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition? Thanks, ... 1 vote 1 answer 147 views ### Why does this algorithm not have an exponential complexity? In this article : Kinodynamic Motion Planning B. Donald, P. Xavier, J. Canny, J. Reif https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf The authors present a PTAS algorithm that can ... 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 \...
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 ...