# Questions tagged [approximation-algorithms]

425 questions
Filter by
Sorted by
Tagged with
234 views

### Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$...
211 views

### Clustering in sublinear time/query

Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy: 1) Minimizing the number of balls that are required to cover all ...
110 views

### Combinatorial algorithm for load balancing

I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine). This is basically a load balancing problem using ...
46 views

### inapproximability of logarithic factor of indepence set [closed]

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
104 views

1k views

### Greedy MAX SAT approximation ratio

Consider a naive MAX SAT approximation algorithm: pick a literal $l$ which appears in maximum number of clauses set the corresponding variable of $l$, such that all clauses containing $l$ are ...
308 views

### Set packing with maximum coverage objective

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
243 views

### Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. I'm interested in the approximability of two problems, or in ...
80 views

### Bellman principle and approximability

Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
547 views

### Proof for ACYCLIC PARTITION being NP-complete

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
1k views

### How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-...
511 views

### Is DAG subset sum approximable?

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
715 views

### Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
374 views

### Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to ...
200 views

### FPRAS for Perfect Matching

If you have FPRASes for counting number of matchings of size $\leq n$ and size $\leq n-1$, can you get an FPRAS for counting number of matchings of size $n$ (i.e perfect matchings)?
65 views

223 views

### Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient ...
7k views

### Top-k frequent items in data stream

Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set. I am thinking about ...
126 views

### Tiling a rectangle with weighted cells (min-max problem)

Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by ...
Notations $\alpha(G) =$ Max sized independent set of graph $G$. $n(G) =$ Number of vertex in graph $G$. Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$, \...