# Questions tagged [approximation-algorithms]

450 questions
Filter by
Sorted by
Tagged with
292 views

### Fuzzy K-modes clustering how to find the cluster centers

I'm trying to understand [fuzzy k-modes] algorithm (look mainly at page 3) in order to implement it. I'm stuck at the calculation of cluster centers they said as shown in the link https://...
665 views

### Is Max-Cut APX-complete on triangle-free graphs?

In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible. Max-Cut is APX-...
356 views

### Finding largest closest subsets

Original question: Base problem: Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose subsets $s_i$ ($i=1,...,N$) from $A$. Elements cannot be repeated within ...
158 views

### Local Smoothness vs optimisation in combinatorial problems

Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
311 views

### k-clustering problems

I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are: Is Euclidean max cut solvable in polynomial time? If not, how well ...
366 views

### A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness. Problem: Given a graph $G(V,E)$, ...
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 ...
679 views

### Building a decision tree to approximate a known function (not to learn an unknown function)

I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$. I would like to approximate $f$ using a decision tree. Up to now I have only found literature in the ...
546 views

### Difference between Primal Dual Algorithm for Proper and Uncrossable Functions

Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions: (1) super-modular functions (2) proper functions ...
279 views

### A approximation version of the Goldreich-Levin Theorem

A little introduction The Goldreich-Levin Theorem says that let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core ...
75 views

### A question regarding Improved Algorithm for Degree Bounded Survivable Network Design Problem

In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis, have used the iterated rounding approach in a similar as by Jain in designing the ...
263 views

### Results regarding Bounded Diameter Minimum Spanning Tree

Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of ...
154 views

### log(OPT) approximation for directed balanced vertex separator

Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of ...
238 views

### Connectivity Problem

Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin. Given undirected graph along with some ...
279 views

### 3 colorable graphs

I was trying to understand the underlying difficulty of coloring 3 colorable graphs with as least number of colors as possible. Though i am aware of hardness result of coloring it with 4 colors, i ...
1k views

### Max-cut via linear programming or sdp

I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is ...
127 views

### Finding an index set so that row sums are positive

Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of ...
1k views

### Relation between fixed parameter and approximation algorithm

Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed ...
486 views

### Dimensionality reduction with slack?

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
338 views

### Hardness of additive approximation to Graph Coloring problem.

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the ...
262 views

### Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
918 views

### Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.
198 views

### Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP

The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall ...
595 views

### Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
530 views

### Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)

Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same. First, I will define a few ...
436 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. ...
822 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)?
392 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, ...
424 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 ...
606 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-...
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 ...
451 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 ...
502 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 ...
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, ...
757 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 ...
225 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 ...
458 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 ...
547 views

### Is there parallel algorithm for 3SAT

Is there any parallel algorithms or approximation algorithms for 3SAT?
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$ ...