Skip to main content

Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

Filter by
Sorted by
Tagged with
1 vote
0 answers
160 views

Is finding the best permutation an NP-Complete problem?

We have a matrix $M$ of size $n$ by $n$ where $M[i][j] \ge 0$ and $M[i][i] = 0$. We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that $$ \...
Amir's user avatar
  • 544
0 votes
0 answers
27 views

Efficient PTAS for 2 identical knapsacks?

Input: $v_1,v_2,...,v_n$ item profits, $0<w_1,w_2,...,w_n\leq1$ item weights. Output: $B_1,B_2$ which are subsets of $\{1,2,...,n\}$ s.t. they are disjoint, and such that $\forall i\in\{1,2\}:\sum_{...
alon's user avatar
  • 1
2 votes
0 answers
58 views

Do prefix hash functions work well for approximate counting?

Given some set $S \subseteq \{0,1\}^n$, suppose we want to approximate $|S|$. One approach is hashing-based approximate counting, which exploits the structure of hash functions to approximately halve $...
Germ's user avatar
  • 191
1 vote
0 answers
61 views

Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

In the maximum coverage problem (also known as max k-cover) we are given a universe $U = \{e_1,\ldots, e_n\}$ of elements, a collection $F = \{S_1,\ldots, S_m\} \subseteq 2^U$ of sets over $U$, and an ...
John's user avatar
  • 412
3 votes
0 answers
54 views

Partial Hamiltonian Path Optimization Problem

Let $G = (V,E)$ be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in $G$ of maximum cardinality, such that (i) the in-degree and out-degree of each ...
John's user avatar
  • 412
3 votes
1 answer
119 views

How well can shortest common supersequence over small alphabet size be approximated?

Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
Hao S's user avatar
  • 228
0 votes
0 answers
55 views

Shortest sequence that contains a given list of sequences as subsequences

Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences? Very similar to the question ...
Hao S's user avatar
  • 228
2 votes
0 answers
79 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
pyridoxal_trigeminus's user avatar
4 votes
0 answers
94 views

Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash ...
Germ's user avatar
  • 191
5 votes
1 answer
195 views

What infinite sums cannot be approximated in polynomial time?

The following is from the book Geometric algorithms and combinatorial optimization: It shows an infinite sum that has an FPTAS (= an $\epsilon$-approximation can be computed using poly($1/\epsilon$) ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
42 views

Hardness of Coloring based on a Black-Box Hardness of Independent Set

It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent ...
John's user avatar
  • 412
3 votes
0 answers
106 views

maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
John's user avatar
  • 412
1 vote
1 answer
116 views

A variant of the generalised assignment problem

I am trying to solve this problem: There are $N$ workers and $T$ tasks. Each task can be assigned to at most one worker. Each worker can be assigned any number of tasks. The profit obtained by ...
Michael C.'s user avatar
0 votes
0 answers
53 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$...
Recursion's user avatar
0 votes
0 answers
30 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 ...
Derek's user avatar
  • 1
1 vote
0 answers
45 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)$....
Edee's user avatar
  • 111
1 vote
3 answers
126 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$....
Winky's user avatar
  • 11
3 votes
0 answers
88 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 ...
a3nm's user avatar
  • 9,677
6 votes
0 answers
293 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 \...
Erel Segal-Halevi's user avatar
2 votes
1 answer
125 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 ...
eden hartman's user avatar
3 votes
0 answers
49 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 ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
46 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
149 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 ...
user69908's user avatar
0 votes
0 answers
28 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 ...
user135520's user avatar
6 votes
1 answer
360 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{...
Thomas Ahle's user avatar
5 votes
1 answer
159 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 ...
Display name's user avatar
-1 votes
1 answer
76 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 ...
john doe's user avatar
4 votes
0 answers
54 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 ...
Mark Schultz-Wu's user avatar
0 votes
1 answer
91 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 ...
Exulansis's user avatar
5 votes
0 answers
87 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
70 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 ...
Rohan Bali's user avatar
0 votes
0 answers
92 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 ...
John's user avatar
  • 412
4 votes
1 answer
191 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
194 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 ...
John's user avatar
  • 412
2 votes
1 answer
64 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$,...
AAArAAA's user avatar
  • 23
2 votes
0 answers
67 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 ...
Karagounis Z's user avatar
1 vote
1 answer
60 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 ...
ErroR's user avatar
  • 210
2 votes
0 answers
134 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 ...
user3508551's user avatar
  • 1,153
1 vote
0 answers
56 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 ...
Sandip's user avatar
  • 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 $\...
David's user avatar
  • 1
4 votes
0 answers
85 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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
71 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 ...
Serge's user avatar
  • 111
1 vote
0 answers
54 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)$ ...
Com's user avatar
  • 41
1 vote
0 answers
73 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. ...
Yly's user avatar
  • 111
6 votes
1 answer
148 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 \...
user3508551's user avatar
  • 1,153
0 votes
0 answers
135 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) ...
John's user avatar
  • 412
0 votes
0 answers
96 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 ...
user135520's user avatar
1 vote
1 answer
174 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 ...
Bell's user avatar
  • 53
3 votes
1 answer
144 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 ...
kostrykin's user avatar
  • 139
1 vote
0 answers
92 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 ...
Julien Codsi's user avatar

1
2 3 4 5
11