With the rapid growth of graph datasets over the past decade, a new kind of
dynamic algorithm, supporting the ability to ingest batches of updates and
exploit parallelism is needed in order to efficiently process large streams of
updates. In this paper, we study batch and parallel algorithms for the dynamic
connectivity problem, a fundamental problem that has received considerable
attention in sequential setting. Perhaps the best known sequential algorithm is
the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which
achieves $O(\log^2 n)$ amortized time per edge insertion or deletion, and
$O(\log n)$ time per query.
In this paper, we design a parallel batch-dynamic connectivity algorithm that
is work-efficient with respect to the HDT algorithm for small batch sizes, and
is asymptotically faster when the average batch size is sufficiently large.
Given a sequence of batched updates, where $\Delta$ is the average batch size
of all deletions, our algorithm achieves $O(\log n \log(1 + n / \Delta))$
expected...

more |
pdf
| html
None.

pkhuong:
Parallel increments processing for batched updates (phat lambda ;). I like this model! https://t.co/YbOv9IwY7v

okateim:
2019/03/22 [3]
Parallel Batch-Dynamic Graph Connectivity (https://t.co/5gTsdcjuOJ)

ComputerPapers:
Parallel Batch-Dynamic Graph Connectivity. https://t.co/nCZfD65oW6

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 14022

Unqiue Words: 2596

This work presents an empirical analysis of exact algorithms for the
unbounded knapsack problem, which includes seven algorithms from the
literature, two commercial solvers, and more than ten thousand instances. The
terminating step-off, a dynamic programming algorithm from 1966, presented the
lowest mean time to solve the most recent benchmark from the literature. The
threshold and collective dominances are properties of the unbounded knapsack
problem first discussed in 1998, and exploited by the current state-of-the-art
algorithms. The terminating step-off algorithm did not exploit such dominances,
but has an alternative mechanism for dealing with dominances which does not
explicitly exploits collective and threshold dominances. Also, the pricing
subproblems found when solving hard cutting stock problems with column
generation can cause branch-and-bound algorithms to display worst-case times.
The authors present a new class of instances which favors the branch-and-bound
approach over the dynamic programming approach but do not...

more |
pdf
| html
None.

okateim:
2019/03/22 [1]
An empirical analysis of exact algorithms for the unbounded knapsack problem (https://t.co/11PYWgszHq)

ComputerPapers:
An empirical analysis of exact algorithms for the unbounded knapsack problem. https://t.co/EMfMM4Kyhk

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 16608

Unqiue Words: 3644

Let $R$ and $B$ be two point sets in $\mathbb{R}^d$, with $|R|+ |B| = n$ and
where $d$ is a constant. Next, let $\lambda : R \cup B \to \mathbb{N}$ such
that $\sum_{r \in R } \lambda(r) = \sum_{b \in B} \lambda(b)$ be demand
functions over $R$ and $B$. Let $\|\cdot\|$ be a suitable distance function
such as the $L_p$ distance. The transportation problem asks to find a map $\tau
: R \times B \to \mathbb{N}$ such that $\sum_{b \in B}\tau(r,b) = \lambda(r)$,
$\sum_{r \in R}\tau(r,b) = \lambda(b)$, and $\sum_{r \in R, b \in B} \tau(r,b)
\|r-b\|$ is minimized. We present three new results for the transportation
problem when $\|r-b\|$ is any $L_p$ metric:
- For any constant $\varepsilon > 0$, an $O(n^{1+\varepsilon})$ expected time
randomized algorithm that returns a transportation map with expected cost
$O(\log^2(1/\varepsilon))$ times the optimal cost.
- For any $\varepsilon > 0$, a $(1+\varepsilon)$-approximation in
$O(n^{3/2}\varepsilon^{-d} \operatorname{polylog}(U)
\operatorname{polylog}(n))$ time, where $U = \max_{p\in R\cup...

more |
pdf
| html
None.

arxiv_org:
Faster Algorithms for the Geometric Transportation Problem. https://t.co/QbkqGjXmpN https://t.co/dSjTdjRZVZ

okateim:
2019/03/21 [3]
Faster Algorithms for the Geometric Transportation Problem (https://t.co/smKJNXrs2o)

ComputerPapers:
Faster Algorithms for the Geometric Transportation Problem. https://t.co/35WfwMwqvz

jaialkdanel:
RT @arxiv_org: Faster Algorithms for the Geometric Transportation Problem. https://t.co/QbkqGjXmpN https://t.co/dSjTdjRZVZ

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 18005

Unqiue Words: 2970

Risk-limiting post election audits guarantee a high probability of correcting
incorrect election results, independent of why the result was incorrect.
Ballot-polling audits select ballots at random and interpret those ballots as
evidence for and against the reported result, continuing this process until
either they support the recorded result, or they fall back to a full manual
recount. For elections with digitised scanning and counting of ballots, a
comparison audit compares randomly selected digital ballots with their paper
versions. Discrepancies are referred to as errors, and are used to build
evidence against or in support of the recorded result. Risk-limiting audits for
first-past-the-post elections are well understood, and used in some US
elections. We define a number of approaches to ballot-polling and comparison
risk-limiting audits for Instant Runoff Voting (IRV) elections. We show that
for almost all real elections we found, we can perform a risk-limiting audit by
looking at only a small fraction of the total ballots...

more |
pdf
| html
None.

okateim:
2019/03/22 [2]
Risk-Limiting Audits for IRV Elections (https://t.co/FRY2Ng1SX7)

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 14949

Unqiue Words: 2678

We prove a convergence guarantee on the unadjusted Langevin algorithm for
sampling assuming only that the target distribution $e^{-f}$ satisfies a
log-Sobolev inequality and the Hessian of $f$ is bounded. In particular, $f$ is
not required to be convex or have higher derivatives bounded.

more |
pdf
| html
None.

arxivml:
"Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices",
Santosh S． Vempala, Andre Wibisono
https://t.co/t1zQ3xUZRu

mathPRb:
Santosh S. Vempala, Andre Wibisono : Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices https://t.co/gRbA5plmdv https://t.co/sSUdNFfaej

okateim:
2019/03/21 [1]
Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices (https://t.co/mVTefxJ8ik)

arxiv_cs_LG:
Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices. Santosh S. Vempala and Andre Wibisono https://t.co/AKsgV5hZkU

StatsPapers:
Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices. https://t.co/p2LT6iz9UX

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 6348

Unqiue Words: 1461

Train marshalling is the process of reordering the railcars of a train in
such a way that the railcars with the same destination appear consecutively in
the final, reassembled train. The process takes place in the shunting yard by
means of a number of classification tracks. In the Train Marshalling Problem
(TMP), the objective is to perform this rearrangement of the railcars with the
use of as few classification tracks as possible. The problem has been shown to
be NP-hard, and several exact and approximation algorithms have been developed
for it. In this paper, we propose a novel exact dynamic programming (DP)
algorithm for the TMP. The worst-case time complexity of this algorithm (which
is exponential in the number of destinations and linear in the number of
railcars) is lower than that of the best presently available algorithm for the
problem, which is an inclusion-exclusion-based DP algorithm. In practice, the
proposed algorithm can provide a substantially improved performance compared to
its inclusion-exclusion-based...

more |
pdf
| html
None.

okateim:
2019/03/21 [2]
A Novel Dynamic Programming Approach to the Train Marshalling Problem (https://t.co/2BATwsDhlF)

Train Marshalling Problem (TMP)

Stargazers: 0

Subscribers: 0

Subscribers: 0

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 2

Total Words: 10289

Unqiue Words: 2184

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 99,586 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible