Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
0
votes
0
answers
39
views
Approximation ratio of randomized rounding for integral multi-commodity flow
In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
-2
votes
0
answers
41
views
Greedy rounding technique
I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for ...
- 1
-1
votes
0
answers
23
views
Finding an algorithm EF[1,1] and PO division for more than two agents
From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.
We consider the problem of fairly and efficiently ...
- 99
1
vote
1
answer
237
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
CommunityBot
- 1
1
vote
3
answers
88
views
Stable/Robust Traveling Salesman Approximation Methods
I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x_1, ..., x_n$ and the set $G^* = G \cup x_{n+1}$, where $x_i$ are points in $R^d$....
- 9,595
0
votes
0
answers
28
views
FPTAS for switching deals
The local supermarket offers seasonal deals on their apples and oranges. You want either apples or oranges on any given day, but don't know until you wake up; you want to
minimise your cost. You ...
- 1
1
vote
0
answers
41
views
How to understand this evolutionary algorithm lower bound calculation?
I have a proof that I understand the most of it except one step
Lemma 10. The expected number of steps the $(1+1)$ EA takes to optimize a linear function with all non-zero weights is $\Omega(n \ln n)$....
- 111
1
vote
1
answer
82
views
Approximating the utilitarian welfare minus a constant
Assume we have $n$ agents and $m$ indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.
Denote the set of allocations by $\mathcal{A}$ and the ...
CommunityBot
- 1
3
votes
0
answers
68
views
FPRAS to estimate the probability to get a cyclic subgraph of a directed graph
Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge ...
- 8,896
1
vote
1
answer
103
views
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
CommunityBot
- 1
6
votes
0
answers
268
views
Techniques for solving huge linear programs
During the solution of some computational problem, we have arrived at a linear program of the following form:
\begin{align*}
\text{maximize} ~~ c x
\\
\text{subject to} ~~ A x \leq b, x \geq 0
\...
- 2,086
29
votes
4
answers
1k
views
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a ...
- 8,896
3
votes
0
answers
44
views
Approximate decomposition of a many-to-one assignment
Suppose we have $n$ items and $n$ agents and we want to assign one item to each agent. We have a probability matrix $P$ such that $p_{i,j}$ is the probability that agent $i$ gets item $j$. If $\sum_j ...
- 2,086
2
votes
0
answers
43
views
Submodulare welfare maximization: is an additive approximation algorithm known?
Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as ...
- 2,086
0
votes
1
answer
332
views
A k-approximation to k-way number partitioning
The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, ...
CommunityBot
- 1
0
votes
0
answers
25
views
Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent
I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative ...
- 111
5
votes
1
answer
147
views
Finding $k \times k$ rectangle in a matrix with maximum sum
Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$
I expect the problem to be NP-hard, so I want a polynomial ...
- 1,868
0
votes
1
answer
56
views
Generalized assignment problem with overall budget
The problem has N tasks. We have M workers. We have the cost of assigning task i to worker j. We have a profit for assigning task i to worker j. We want to assign each task to exactly one worker. One ...
CommunityBot
- 1
6
votes
1
answer
342
views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 4,681
-1
votes
1
answer
74
views
Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$
I am able to solve this using brute force but curious if there is a better approach.
Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
- 28.3k
3
votes
1
answer
135
views
Approximative counting of matchings in a graph
The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
- 11
0
votes
0
answers
35
views
Using an offline approximation algorithm within an online algorithm
When defining an online algorithm, it is common to assume that there exists an optimal offline algorithm to be used over the set of already known requests.
For example, consider the IGNORE algorithm ...
2
votes
0
answers
49
views
Approximate Matrix Multiplication with approximation guarantees that ignore large elements?
Approximate matrix multiplication is a technique to replace a matrix product $A^t B$ with a smaller product $(\Pi A)^t(\Pi B)$.
Intuitively, if $\Pi$ is chosen from a suitable distribution that has
...
- 918
5
votes
0
answers
78
views
A simultaneous FPTAS for both max-min and min-max number partitioning
The multiway number partitioning problem has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to ...
- 2,086
0
votes
0
answers
39
views
Why are impossibility results harder for uniform sparsest cut than non-uniform?
My question is this: why is it the case that the uniform cost version of the Sparsest Cut problem has eluded hardness of approximation results whereas the non-uniform version has not; my intuition is ...
- 9
0
votes
0
answers
56
views
Bin Covering problem with variable bin sizes
I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can ...
0
votes
0
answers
88
views
When Exponential Costs are Essential for NP-Hardness?
In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
- 173
4
votes
1
answer
180
views
Computing an approximate root of a two-dimensional monotone function
Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
- 321
1
vote
1
answer
159
views
3 Matroid Intersection, a Special Case
It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.
Question: Does this problem remain NP-Hard if one of the matroids ...
- 4,367
0
votes
0
answers
75
views
Finding lightest k elements in data stream using small space
There has been much research and progress devoted towards algorithms for finding approximate $\ell_p$-Heavy Hitters with parameter $\epsilon$ in the streaming setting (For all 3 of the vanilla, ...
- 1
9
votes
4
answers
1k
views
Planted Clique in G(n,p), varying p
In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be ...
- 11
2
votes
1
answer
61
views
Balls in monochromatic bins
Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
- 11.7k
2
votes
0
answers
66
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 607
1
vote
1
answer
55
views
$k-$median problem and filtering technique Lin and Vitter
I read a paper from Tardos et al. about $k-$medians in metric space problem:
Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point ...
- 9,595
2
votes
0
answers
111
views
Why is the competitive ratio defined as $\mathbb{E}(ALG)/\mathbb{E}(OPT)$ vs $\mathbb{E}(ALG/OPT)$?
It seems like the consensus is to define an $\alpha$-competitive algorithm if $\mathbb{E}_R(ALG) \geq \alpha \mathbb{E}_R(OPT)$ where $\mathbb{E}_R$ is the expected value taken across the problem ...
- 1,078
1
vote
0
answers
52
views
Approximation algorithm for non-bipartite Euclidean matching
What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are ...
- 11
0
votes
1
answer
76
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 9,595
8
votes
2
answers
1k
views
Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed
The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
CommunityBot
- 1
6
votes
2
answers
893
views
Maximizing difference of a submodular and a modular function
I'm considering a network planning problem which is stated as follows:
From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that
\begin{equation}
f(\mathcal{A}) - \...
- 1
5
votes
1
answer
190
views
Hashing-based vs almost uniform sampling-based approximate counting
Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:
For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
CommunityBot
- 1
3
votes
0
answers
58
views
Submodular welfare maximization: what is the best known approximation ratio of a deterministic algorithm?
In the submodular welfare maximization problem, there is a set $M$ of items that should be partitioned among $n$ agents. Each agent $i$ has a value function $v_i: 2^M\to \mathbb{R}_+$. All value ...
- 2,086
0
votes
0
answers
45
views
Maximum independent set in "subgraph-claw-free" graphs
A $d$-claw in a graph is a set of $d+1$ vertices, one of which (the "center") is connected to the other $d$, but the other $d$ are not connected to each other. A graph is called $d$-claw ...
- 2,086
0
votes
1
answer
68
views
Proper terminology for input, parameter or variable fixing. Refinement? Projection? Fixation? Partial valuation?
I contemplate writing a paper on automating fixing some inputs/parameters to specific values in a kind of workflow/pipeline definition language/system and looking for best terminology.
English is not ...
- 111
0
votes
2
answers
360
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, Is there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized?
Note that, heaviest edge ...
- 194
0
votes
0
answers
23
views
Is there a theoretical runtime guarantee to eigen decomposition (up to some convergence distance)?
I'm familiar with the QR algorithm for eigen decomposition in symmetric matrices, which takes roughly O(n^3) time. But that O(n^3) only holds if you take a constant number of QR steps per eigenvalue, ...
- 101
1
vote
0
answers
52
views
Better approximation of the subset in the membership oracle
A standard tool for estimating the size of a subset via membership oracle queries is given below.
Lemma 2.8: . Consider two (finite) sets $B ⊆ U$, where $n = |U|$. Let $ε ∈ (0, 1)$ and $γ ∈ (0, 1/2)$ ...
- 41
1
vote
0
answers
71
views
How to enforce convexity?
I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...
- 111
15
votes
1
answer
949
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
CommunityBot
- 1
6
votes
1
answer
139
views
Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$
This is a cross-post from a question I asked on cs.stackexchange 2 weeks ago with no answers. I thought it might find home here.
We are given sorted $0\leq x_1 \leq x_2 \leq \dots \leq x_n$ and $y_1 \...
- 16.8k
0
votes
0
answers
93
views
Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?
In the knapsack (KP) problem we are given a set $I = \{1,\ldots,n\}$ of items, each item $i \in [n]$ has a weight $w_i$ and a profit $p_i$. A classic Fully Polynomial time approximation scheme (FPTAS) ...
- 173