Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
4 views

Proof that there isnt a c-additive approximation to Partition Problem

Define Partition = { x1, x2, x3,....,xn| there is a division to two groups in which the sums of the two groups are equal} is there a proof that there isnt an additive approximation algorithm to the ...
0
votes
0answers
12 views

Relationship between IID and Random Order Inputs

I am currently working on a project where we hope to find $(1-\epsilon)$ competitive ratio algorithms for an online problem (subject to certain largeness assumptions) in both the IID and random order ...
1
vote
0answers
35 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 ...
2
votes
2answers
83 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. ...
1
vote
0answers
32 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
0answers
38 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 \...
5
votes
1answer
77 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 ...
3
votes
1answer
141 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 ...
1
vote
1answer
33 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
0answers
27 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
1answer
44 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 ...
0
votes
1answer
22 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. ...
0
votes
1answer
23 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 ...
0
votes
0answers
17 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?
0
votes
0answers
13 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, ...
0
votes
0answers
101 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. ...
1
vote
0answers
39 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| ...
1
vote
1answer
28 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$ ...
2
votes
1answer
52 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 ...
0
votes
0answers
11 views

Proof of lemma for competitive ratio on subsequence - Strip Packing

In this paper by Azar and Epstein in Section 4 they consider online strip packing of rectangles without rotation in a setting where when a rectangle arrives it has to be lowered monotonically ...
0
votes
0answers
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'...
2
votes
1answer
79 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 ...
0
votes
0answers
23 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{...
0
votes
1answer
36 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
1answer
21 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) ...
1
vote
0answers
36 views

Approximation classes for optimization problems with real values

Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.? If my understanding is correct a ...
2
votes
0answers
53 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
0
votes
1answer
42 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
0
votes
1answer
34 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?
1
vote
0answers
45 views

How is "expected approximation ratio" defined in cases when the expected value of the optimal solution is known?

Consider an approximation algorithm which does better than $f(n)$, in expectation. Suppose we know that $\mathbb{E}(OPT)=g(n)$. Given that we use the convention of "larger divided by smaller"...
7
votes
1answer
106 views

What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
0
votes
0answers
47 views

Fast text comparison algorithm for long texts

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
0
votes
0answers
16 views

Voice activation keywords algorithms on iot devices?

I've been scouting the internet for days and after a lot of digging, I decided to resort to my last hope and ask: I'm talking about the "hey Google", "Alexa" and so on voice ...
0
votes
1answer
134 views

How to determine the approximation factor for greedy vertex cover algorithm?

The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left. Formally: $\text{GreedyVertexCover}...
1
vote
1answer
38 views

Hitting set approximation

I'm having a small problem understanding what is the result of the 4-approximation polynomial-time algorithm for 4-Hitting Set. What I mean is that by solving 4-Hitting set I get a group X such that ...
1
vote
1answer
23 views

Trouble to understand the proof of greedy algorithm for set cover

Problem definition: Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \{S_1,..., S_k\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that ...
0
votes
0answers
60 views

Approximate FPT and Approximate kernel for a decidable problem

I'm trying to prove the following: For every decidable parameterized problem Π, Π admits a fixed parameter tractable α-approximation algorithm if and only if Π has an α-approximate kernel. I'm trying ...
0
votes
0answers
44 views

Connection between planar graph and vertex cover

I have two similar problems in which I'm trying to find a connection to help me solve one of them. In the first one I'm given a graph G = (V,E) , integer k, and vertex cover U of size k. The objective ...
2
votes
1answer
27 views

Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
2
votes
2answers
38 views

Approximate duplicate sampling from a stream

The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal. Design an algorithm that takes in ...
0
votes
1answer
109 views

Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation

As said, I had to prove that the greedy algorithm: Initialize $C = ∅$ Look for an un-covered vertex and add one of its edges to $C$ Repeat 2 while there's uncovered vertices Is a 2-approximation ...
2
votes
0answers
35 views

Optimal allocation of heterogeneous divisible goods

In the context of my PhD on the simulation of the labor market with a multi-agent model, I encoutered a problem that doesn't seem to be really treated in the litterature, according to my searches on ...
1
vote
2answers
51 views

Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
4
votes
2answers
41 views

How do you express a floor / ceiling in the approximation factor of an approximation algorithm?

Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot. Suppose I have some minimisation problem $X$ where, ...
3
votes
1answer
34 views

Approximation of rational sequences via linear recurrences of small order

I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact ...
1
vote
1answer
62 views

Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
0
votes
0answers
21 views

Dominating set in a connected graph

I have a synchronic ring network with $n$ (i.e. the nodes are connected in a ring), and I need a good approximation (factor of 3/2 of the optimal value) for the minimal dominating set. I also need ...
1
vote
1answer
44 views

Communication complexity of equality gap problem

I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by: $$f_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at ...
1
vote
1answer
33 views

Inapproximability of graph problems on a restricted setting

I am considering the following problem $\mathcal{P}$. $\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number ...
2
votes
1answer
96 views

Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...

1
2 3 4 5
11