New answers tagged ds.algorithms
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}}(...
- 800
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
Related Tags
ds.algorithms × 1788graph-algorithms × 329
graph-theory × 278
cc.complexity-theory × 248
reference-request × 238
approximation-algorithms × 161
optimization × 111
co.combinatorics × 109
ds.data-structures × 102
time-complexity × 88
linear-algebra × 62
np-hardness × 61
linear-programming × 59
cg.comp-geom × 57
sorting × 53
randomized-algorithms × 52
matrices × 44
sat × 43
lower-bounds × 33
nt.number-theory × 30
heuristics × 30
directed-acyclic-graph × 28
machine-learning × 27
counting-complexity × 27
complexity-classes × 26