Skip to main content

Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
68 views

Geometric Set Cover in one dimension

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
Sandra's user avatar
  • 63
1 vote
1 answer
236 views

Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size

I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$. If we pick ...
ConScience's user avatar
0 votes
1 answer
112 views

To write an IP and relax it to LP for finding a multi-set in a graph

I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given: A digraph ...
ConScience's user avatar
1 vote
0 answers
24 views

tight lower bounds of parallel machine scheduling with gang scheduling constraint

I am interested in tight bounds for the Parallel Machine scheduling problem with a gang scheduling constraint. In the notation of Graham, Lawler, Lenstra and Rinnooy Kan, this might be called $Pm|\rm{...
Wandering Logic's user avatar
-1 votes
1 answer
794 views

How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover

The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
ConScience's user avatar
0 votes
0 answers
65 views

Bin Packing tight analysis lower bound?

I am having a problem understanding the following: This is the background of the lemma: To prove the lower bounds, we use the classical lower bound construction from [5, 9]. We have an input instance ...
ryan chandra's user avatar
0 votes
0 answers
125 views

How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded

Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
RJ94's user avatar
  • 1
0 votes
0 answers
80 views

asymptotic approximation ratio vs absolute approximation ratio?

I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different ...
ryan chandra's user avatar
0 votes
1 answer
158 views

MAX-SAT approximation factor

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm MAX-3SAT: set every variable with a random value ($0$ or $1$ each ...
Marcus34's user avatar
0 votes
0 answers
44 views

Approximation Class that Decides

Suppose we have a minimization ILP. Denote its value by $OPT$. Let $PER$ be the solution to its LP relaxation. Given a real number $t$, we would like to decide whether $OPT \leq (1+t) \cdot PER$, in ...
Samuel Bismuth's user avatar
0 votes
1 answer
784 views

Traveling salesman problem on an incomplete graph

In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the ...
Rohit Pandey's user avatar
1 vote
0 answers
16 views

Algorithm for minimizing the number of resources simultaneously open while iterating through a series of tasks

I have a problem where I'm iterating through a series of tasks and each task requires that a specific file is loaded into memory. The files are not allowed to be unloaded until all of the tasks that ...
Erotemic's user avatar
  • 123
2 votes
0 answers
68 views

State of the art implementations of minimum-cost multicommodity flow approximation algorithms

I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
fuglede's user avatar
  • 165
3 votes
0 answers
90 views

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$ [closed]

Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \geq y_n \geq 0$ non negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ ...
AspiringMat's user avatar
1 vote
1 answer
26 views

Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?

In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...
EarlyGame's user avatar
1 vote
0 answers
69 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: ...
Yaroslav Bulatov's user avatar
1 vote
2 answers
90 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 $...
Luigi Efour's user avatar
0 votes
0 answers
26 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 ...
nuemlouno's user avatar
1 vote
1 answer
202 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 ...
kostger's user avatar
  • 37
1 vote
1 answer
1k 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 ...
SVMteamsTool's user avatar
-2 votes
1 answer
55 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 ...
imi kim's user avatar
  • 101
1 vote
1 answer
154 views

Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
kostger's 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 ...
advocateofnone's user avatar
0 votes
1 answer
173 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 ...
SVMteamsTool's user avatar
0 votes
1 answer
37 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 ...
tonythestark's user avatar
1 vote
1 answer
77 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 ...
qc6518's user avatar
  • 33
1 vote
0 answers
71 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 ...
qc6518's user avatar
  • 33
1 vote
0 answers
24 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 ...
Azuresonance's user avatar
1 vote
0 answers
72 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 ...
ItsMeTheBee's user avatar
1 vote
1 answer
88 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-...
tonythestark's user avatar
1 vote
1 answer
104 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, ...
Er7's user avatar
  • 53
1 vote
0 answers
84 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 ...
Brian's user avatar
  • 129
1 vote
1 answer
52 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 ...
Alex P's user avatar
  • 148
1 vote
1 answer
74 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}$, ...
Vahagn's user avatar
  • 111
0 votes
0 answers
119 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 ...
zqq's user avatar
  • 69
7 votes
5 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 ...
Lancdorr's user avatar
  • 181
1 vote
0 answers
23 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 ...
rxjs's user avatar
  • 11
1 vote
1 answer
31 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 ...
envy grunt's user avatar
0 votes
1 answer
47 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 ...
Bogdan Vlad's user avatar
1 vote
1 answer
102 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-...
Dan D-man's user avatar
  • 524
1 vote
0 answers
46 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 ...
yellowcard123's user avatar
1 vote
0 answers
271 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 ...
shima's user avatar
  • 111
2 votes
2 answers
173 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. ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
85 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 ...
worldsmithhelper's user avatar
4 votes
0 answers
50 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 \...
Dmitry's user avatar
  • 345
6 votes
1 answer
122 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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
168 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
428 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 ...
rustyshackleford's user avatar
1 vote
0 answers
75 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 ...
leonistgott's user avatar
2 votes
1 answer
163 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 ...
Aristide's user avatar
  • 323

1
2
3 4 5
13