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
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
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$....
- 11
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
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
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 ...
- 91
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
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 ...
- 11
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
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{...
- 958
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 ...
- 151
-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 ...
- 1
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
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 ...
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
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
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 ...
- 2,086
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 ...
- 173
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
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$,...
- 23
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 ...
- 113
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 $\...
- 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
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
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 \...
- 1,078
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
0
votes
0
answers
80
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 111
1
vote
1
answer
128
views
Approximation algorithm for balanced bipartite independent set?
The Problem: Given a bipartite graph $G = (L,R,E)$ with $|L|=|R|=n$, the balanced bipartite independent set problem asks us to output the largest vertex subsets $A\subseteq L, B\subseteq R$ of equal ...
- 53
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 ...
- 139
1
vote
0
answers
72
views
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
- 11
1
vote
0
answers
55
views
Find the minimum cost spider joining a root to some leaves
A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.
I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
- 607
1
vote
1
answer
105
views
Which is the most efficient of the two following approximation algorithms?
Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps
\begin{align*}
\mathrm{Value} &: \mathfrak{B} \to \mathbb{R}
\\
\mathrm{Upper} &: \mathfrak{B}...
- 111
1
vote
0
answers
60
views
The tree augmentation problem, but with hyperlinks
In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
- 607
0
votes
0
answers
122
views
Approximate inclusion-Exclusion?
I am trying to understand or find literature on the following problem of approximate inclusion exclusion.
Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
- 706
0
votes
1
answer
94
views
Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem
Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.
The Shortest Steiner cycle problem is defined ...
- 141
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=...
- 67