Skip to main content

# Questions tagged [approximation]

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

608 questions
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 ...
• 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 ...
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 ...
1 vote
0 answers
24 views

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: ...
1 vote
2 answers
90 views

• 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 ...
• 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 ...
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 ...
• 111
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-...
• 211
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, ...
• 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 ...
• 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 ...
• 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}$, ...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 158
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 ...
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-...
• 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 ...
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 ...
• 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. ...
• 6,070
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 ...
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 \...
• 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 ...
• 6,070
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 ...
• 6,070
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 ...
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 ...
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 ...
• 323