Data Structures and Algorithms

Authors and titles for July 2013

[21] arXiv:1307.2274 [pdf, other]

Title: Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Nicholas J. A. Harvey, Neil Olver

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[22] arXiv:1307.2313 [pdf, other]

Title: Improved Submatrix Maximum Queries in Monge Matrices

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Comments: Appeared in ICALP 2014

Subjects: Data Structures and Algorithms (cs.DS)

[23] arXiv:1307.2347 [pdf, other]

Title: Combinatorial decomposition approaches for efficient counting and random generation FPTASes

Romeo Rizzi, Alexandru I. Tomescu

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[24] arXiv:1307.2415 [pdf, other]

Title: Finding the Minimum-Weight k-Path

Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty

Comments: To appear at WADS 2013

Subjects: Data Structures and Algorithms (cs.DS)

[25] arXiv:1307.2520 [pdf, other]

Title: Fault Tolerant Clustering Revisited

Nirman Kumar, Benjamin Raichel

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[26] arXiv:1307.2521 [pdf, other]

Title: Point Line Cover: The Easy Kernel is Essentially Tight

Stefan Kratsch, Geevarghese Philip, Saurabh Ray

Subjects: Data Structures and Algorithms (cs.DS)

[27] arXiv:1307.2531 [pdf, other]

Title: Better Approximation Bounds for the Joint Replenishment Problem

Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiří Sgall

Subjects: Data Structures and Algorithms (cs.DS)

[28] arXiv:1307.2536 [pdf, other]

Title: Greedy Online Bipartite Matching on Random Graphs

Andrew Mastin, Patrick Jaillet

Subjects: Data Structures and Algorithms (cs.DS)

[29] arXiv:1307.2696 [pdf, other]

Title: Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints

T-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao

Comments: Corrected references in abstract

Subjects: Data Structures and Algorithms (cs.DS)

[30] arXiv:1307.2724 [pdf, other]

Title: The technique of in-place associative sorting

A. Emre Cetin

Comments: 34 Pages. arXiv admin note: substantial text overlap with arXiv:1209.0572, arXiv:1210.1771, arXiv:1209.3668, arXiv:1209.1942, arXiv:1209.4714

Subjects: Data Structures and Algorithms (cs.DS)

[31] arXiv:1307.2735 [pdf, other]

Title: An Efficient Multiplication Algorithm Using Nikhilam Method

Shri Prakash Dwivedi

Comments: Extended version to appear in ITC 2013

Subjects: Data Structures and Algorithms (cs.DS); Symbolic Computation (cs.SC)

[32] arXiv:1307.2806 [pdf, other]

Title: Packing a Knapsack of Unknown Capacity

Yann Disser, Max Klimm, Nicole Megow, Sebastian Stiller

Subjects: Data Structures and Algorithms (cs.DS)

[33] arXiv:1307.2808 [pdf, other]

Title: A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha

Comments: 19 pages

Subjects: Data Structures and Algorithms (cs.DS)

[34] arXiv:1307.2855 [pdf, other]

Title: Flow-Based Algorithms for Local Graph Clustering

Lorenzo Orecchia, Zeyuan Allen Zhu

Comments: A shorter version of this paper has appeared in the proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)

[35] arXiv:1307.2863 [pdf, other]

Title: Dynamic Data Structure for Tree-Depth Decomposition

Zdenek Dvorak, Martin Kupec, Vojtech Tuma

Subjects: Data Structures and Algorithms (cs.DS)

[36] arXiv:1307.3033 [pdf, other]

Title: QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average

Stefan Edelkamp, Armin Weiß

Subjects: Data Structures and Algorithms (cs.DS)

[37] arXiv:1307.3073 [pdf, other]

Title: Finding small patterns in permutations in linear time

Sylvain Guillemot, Dániel Marx

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[38] arXiv:1307.3192 [pdf, other]

Title: Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods

Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, Berthold Vöcking

Subjects: Data Structures and Algorithms (cs.DS)

[39] arXiv:1307.3301 [pdf, other]

Title: Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Vitaly Feldman, Jan Vondrak

Comments: Extended abstract appears in proceedings of FOCS 2013

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Machine Learning (cs.LG)

[40] arXiv:1307.3621 [pdf, other]

Title: A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage

Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio

Subjects: Data Structures and Algorithms (cs.DS)

[41] arXiv:1307.3650 [pdf, other]

Title: Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period

Natashia Boland, Thomas Kalinowski, Simranjit Kaur

Journal-ref: Journal of Combinatorial Optimization, Volume 32, Issue 3, pp 885-905, 2016

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[42] arXiv:1307.3692 [pdf, other]

Title: Parallel Graph Decompositions Using Random Shifts

Gary L. Miller, Richard Peng, Shen Chen Xu

Subjects: Data Structures and Algorithms (cs.DS)

[43] arXiv:1307.3736 [pdf, other]

Title: Prophet Inequalities with Limited Information

Pablo D. Azar, Robert Kleinberg, S. Matthew Weinberg

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[44] arXiv:1307.3757 [pdf, other]

Title: The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online

Albert Gu, Anupam Gupta, Amit Kumar

Comments: An extended abstract appears in the 45th ACM Symposium on the Theory of Computing (STOC), 2013

Subjects: Data Structures and Algorithms (cs.DS)

[45] arXiv:1307.3822 [pdf, other]

Title: A simple approximation algorithm for the internal Steiner minimum tree

Bang Ye Wu

Subjects: Data Structures and Algorithms (cs.DS)