Top 6 Arxiv Papers Today in Data Structures And Algorithms


2.012 Mikeys
#1. Parallel Batch-Dynamic Graph Connectivity
Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala
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
Figures
None.
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 14022
Unqiue Words: 2596

2.006 Mikeys
#2. An empirical analysis of exact algorithms for the unbounded knapsack problem
Henrique Becker, Luciana S. Buriol
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
Figures
None.
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 16608
Unqiue Words: 3644

2.003 Mikeys
#3. Faster Algorithms for the Geometric Transportation Problem
Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, Allen Xiao
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
Figures
None.
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 18005
Unqiue Words: 2970

2.002 Mikeys
#4. Risk-Limiting Audits for IRV Elections
Michelle Blom, Peter J. Stuckey, Vanessa Teague
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
Figures
None.
Tweets
okateim: 2019/03/22 [2] Risk-Limiting Audits for IRV Elections (https://t.co/FRY2Ng1SX7)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 14949
Unqiue Words: 2678

2.0 Mikeys
#5. Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices
Santosh S. Vempala, Andre Wibisono
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
Figures
None.
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6348
Unqiue Words: 1461

1.999 Mikeys
#6. A Novel Dynamic Programming Approach to the Train Marshalling Problem
Hossein Falsafain, Mohammad Tamannaei
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
Figures
None.
Tweets
okateim: 2019/03/21 [2] A Novel Dynamic Programming Approach to the Train Marshalling Problem (https://t.co/2BATwsDhlF)
Github

Train Marshalling Problem (TMP)

Repository: Train-Marshalling-Problem
User: hfalsafain
Language: None
Stargazers: 0
Subscribers: 0
Forks: 0
Open Issues: 0
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 10289
Unqiue Words: 2184

About

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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 99,586 papers.