Tagged Questions

38 views

Brute Force Search Algorithm for Semidefinite Programming (Representation of Spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
57 views

Given oracle for Max-3SAT compute clauses that cannot be satisfied

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
46 views

154 views

309 views

Quantum complexity of maximum inner product search

Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$. Typically $k \ll m, n$ (many ...
231 views

Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
78 views

L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

Recently I read this paper which was published in FOCS2007. In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ...
76 views

Set Cover variant- improvement over log(n) approximation?

Suppose we are asked to produce a set cover of minimal weight, where here w(S)=size(S) (and the weight of the cover is the sum of the weights of its sets). It is well known that in general weighted ...
175 views

What is the reverse of greedy algorithm for setcover?

A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ...
226 views

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
317 views

Complexity of approximating the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$ I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
118 views

72 views

Distributing bags of apples equally

Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...
197 views

Approximation algorithms for the maximum $2$-independence set problem

I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...
97 views

132 views

The complexity of decomposing a bi-stochastic matrix

A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by ...
31 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 ...
78 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 ...
26 views