Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

Filter by
Sorted by
Tagged with
10
votes
2answers
432 views

Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. ...
8
votes
3answers
781 views

Poly-time approximation scheme for problems with pseudo-polynomial time algorithms

The question is: Does a poly-time approximation scheme always exist for NP-complete problems that have pseudo-polynomial time algorithms (like knapsack for example)?
0
votes
0answers
391 views

Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic. What's the reason for this? Are there any related problems, ...
10
votes
1answer
413 views

Examples of hard instances for Goemans and Williamson algorithm

I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor. The algorithm to ...
13
votes
2answers
591 views

Estimating VC-Dimension

What is known about the following problem? Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-...
19
votes
3answers
2k views

Integrality gap and approximation ratio

When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of ...
15
votes
1answer
447 views

Graph decompositions for combining “local” functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
17
votes
3answers
492 views

Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an ...
22
votes
2answers
1k views

Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
11
votes
1answer
721 views

Why do NP-complete problems not have similar approximation ratios?

Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar ...
4
votes
0answers
224 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
5
votes
3answers
447 views

Partitioning a segmented stick

Problem : We are given a stick partitioned into n - equal parts. Each of these parts has a weight, let's say x. Number of times x appears as weight of some part is guaranteed to be even. For ...
3
votes
2answers
530 views
27
votes
4answers
2k views

Bounded-cardinality bounded-frequency set cover: hardness of approximation

Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets. Example: the case $k = 4$ ...
12
votes
3answers
561 views

What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution? I know one such example for permutation flow shop problem $F|perm|C_{max}...
7
votes
3answers
2k views

A simple approximation algorithm for the TSP

Consider the following extremely simple approximation algorithm for the TSP. Input: A complete weighted graph $G=(V,E).$ Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$ While there ...
12
votes
3answers
701 views

A Multi-cut Problem

I'm looking for a name or any references to this problem. Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
7
votes
2answers
795 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 ...
19
votes
1answer
345 views

What are the best possible time/error tradeoffs for approximate solution of linear programs?

For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity ...
17
votes
2answers
762 views

Set Cover for Permutation Matrices

Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has ...
10
votes
1answer
225 views

Relaxing $\ell_0$ constraints in an optimization

I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ ...
26
votes
3answers
953 views

When is relaxed counting hard?

Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
8
votes
2answers
350 views

complexity of fitting models to data

Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function $x_1 \ldots x_n$ is a set of real values, and we'd like to compute $\text{argmin}_a \sum_i f(a,x_i)$ to ...
11
votes
2answers
509 views

Average distortion embeddings

Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$. Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to ...
5
votes
1answer
417 views

High probable polynomial time algorithm for NP-hard problems?

Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the ...

1
5 6 7 8
9