New answers tagged

1 vote
Accepted

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Here's an elaboration on my comment, assuming I didn't get lost in all the notation above: For $\mathfrak{S}=\mathcal{P}([n])$, the power set of $[n]$, it holds that \begin{equation*} f_{\mathfrak{S}}(...
1 vote

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Disclaimer. This is just to provide some details for Yuri's nice response to Q3, and generalize it to arbitrary group sizes. Let $n=p_1 + \ldots + p_k$ be a partition of $n$ in to $k \ge 1$ positive ...
  • 291
4 votes
Accepted

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $z$ be the coordinate-wise product of $x$ and $y$; that is, $z_i = x_i y_i$ for all $i$. Then we need to compute $\sum_{S\in {\cal S}} z_S$. Q1: We can solve the problem using dynamic programming. ...
  • 3,899
2 votes
Accepted

$k-$median problem and filtering technique Lin and Vitter

Consider any fixed location $j$. For any given center $i$, let $X_{ij}$ be the fraction of demand from location $j$ assigned to $i$. Let $d_{ij}$ be the distance from location $j$ to $i$. The LP has ...
  • 9,380

Top 50 recent answers are included