Unanswered Questions
210 questions with no upvoted or accepted answers
0
votes
0
answers
42
views
Different version of approximation complexity and algorithm for densest-k-subgraph problem
In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
0
votes
0
answers
33
views
On approx-preserving P- and A-reducibilities
Let $X$ and $Y$ be two NPO problems.
Let $(f,g)$ be a reduction between $X$ and $Y$,
in particular, assume that $(f,g)$ is both P-reduction and A-reduction,
i.e.,
there exist two poly-time ...
- 650
0
votes
0
answers
134
views
Maximize number of bins and minimize cost of elements chosen from a set
I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
- 101
0
votes
0
answers
245
views
Steiner Tree and minimum spanning tree
If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
- 11
0
votes
0
answers
88
views
Approximation Algorithm for TSP-like problem
Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with ...
- 461
0
votes
0
answers
216
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 ...
- 639
0
votes
0
answers
114
views
How can I show that zero-one programming is not in APX?
How can I show that zero-one programming is not in APX?
Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the
zero-one programming problem to Vertex Cover and show that ...
0
votes
0
answers
278
views
Calculating exact/approximate solution to a formula
Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.
Consider ...
- 749
0
votes
0
answers
203
views
Finding assignment-minimum complete k-partite graph cover
Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs?
I'm assuming this problem is NP-...
- 916
0
votes
0
answers
89
views
Partitioning based on distribution
Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution.
For two bins and uniform distribution, this problem is ...
CommunityBot
- 1
0
votes
0
answers
133
views
Approximation algorithms based on relaxing a feasible to infeasible solution?
A lot of approximation algorithms are based on relaxation. The way it usually works is this. You take the original problem and relax it some large class of efficiently solvable problem (e.g. relax an ...
- 3,548
0
votes
0
answers
307
views
Fuzzy K-modes clustering how to find the cluster centers
I'm trying to understand [fuzzy k-modes][1] 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://...
CommunityBot
- 1
0
votes
0
answers
425
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, ...
- 11.6k
-1
votes
1
answer
132
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 ...
- 31
-1
votes
1
answer
77
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 ...
- 29.5k