Data Structures and Algorithms

Authors and titles for July 2013

[51] arXiv:1307.4355 [pdf, other]

Title: Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b--Matching Problems in Nonbipartite Graphs

Kook Jin Ahn, Sudipto Guha

Subjects: Data Structures and Algorithms (cs.DS)

[52] arXiv:1307.4359 [pdf, other]

Title: Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints

Kook Jin Ahn, Sudipto Guha

Subjects: Data Structures and Algorithms (cs.DS)

[53] arXiv:1307.4473 [pdf, other]

Title: Approximating the minimum cycle mean

Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer

Comments: In Proceedings GandALF 2013, arXiv:1307.4162

Journal-ref: EPTCS 119, 2013, pp. 136-149

Subjects: Data Structures and Algorithms (cs.DS)

[54] arXiv:1307.4518 [pdf, other]

Title: Ranking with Diverse Intents and Correlated Contents

Jian Li, Zeyu Zhang

Comments: 14 pages

Subjects: Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR)

[55] arXiv:1307.4521 [pdf, other]

Title: Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

Adam Kasperski, Pawel Zielinski

Comments: arXiv admin note: text overlap with arXiv:1305.5339

Subjects: Data Structures and Algorithms (cs.DS)

[56] arXiv:1307.4543 [pdf, other]

Title: Complete Solutions for a Combinatorial Puzzle in Linear Time

Lei Wang, Xiaodong Wang, Yingjie Wu, Daxin Zhu

Subjects: Data Structures and Algorithms (cs.DS)

[57] arXiv:1307.4927 [pdf, other]

Title: Linear-Time FPT Algorithms via Network Flow

Yoichi Iwata, Keigo Oka, Yuichi Yoshida

Comments: 20 pages

Subjects: Data Structures and Algorithms (cs.DS)

[58] arXiv:1307.5108 [pdf, other]

Title: Polynomiality for Bin Packing with a Constant Number of Item Types

Michel X. Goemans, Thomas Rothvoss

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

[59] arXiv:1307.5290 [pdf, other]

Title: Jamming-Resistant Learning in Wireless Networks

Johannes Dams, Martin Hoefer, Thomas Kesselheim

Comments: 22 pages, 2 figures, typos removed

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

[60] arXiv:1307.5296 [pdf, other]

Title: First-Come-First-Served for Online Slot Allocation and Huffman Coding

Monik Khare, Claire Mathieu, Neal E. Young

Comments: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014

Subjects: Data Structures and Algorithms (cs.DS); Information Theory (cs.IT)

[61] arXiv:1307.5299 [pdf, other]

Title: Polymatroid Prophet Inequalities

Paul Duetting, Robert Kleinberg

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

[62] arXiv:1307.5547 [pdf, other]

Title: Linear-Time Recognition of Probe Interval Graphs

Ross M. McConnell, Yahav Nussbaum

Subjects: Data Structures and Algorithms (cs.DS)

[63] arXiv:1307.5582 [pdf, other]

Title: Random Rates for 0-Extension and Low-Diameter Decompositions

Anupam Gupta, Kunal Talwar

Subjects: Data Structures and Algorithms (cs.DS)

[64] arXiv:1307.5697 [pdf, other]

Title: Dimension Reduction via Colour Refinement

Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Optimization and Control (math.OC)

[65] arXiv:1307.5899 [pdf, other]

Title: Optimal Hierarchical Layouts for Cache-Oblivious Search Trees

Peter Lindstrom, Deepak Rajan

Comments: Extended version with proofs added to the appendix

Subjects: Data Structures and Algorithms (cs.DS)

[66] arXiv:1307.5934 [pdf, other]

Title: A Near-Optimal Dynamic Learning Algorithm for Online Matching Problems with Concave Returns

Xiao Alison Chen, Zizhuo Wang

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Optimization and Control (math.OC)

[67] arXiv:1307.6462 [pdf, other]

Title: AliBI: An Alignment-Based Index for Genomic Datasets

Hector Ferrada, Travis Gagie, Tommi Hirvola, Simon J. Puglisi

Subjects: Data Structures and Algorithms (cs.DS); Computational Engineering, Finance, and Science (cs.CE)

[68] arXiv:1307.6505 [pdf, other]

Title: On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

Aleksandar Ilic

Comments: 6 pages, 1 algorithm

Subjects: Data Structures and Algorithms (cs.DS)

[69] arXiv:1307.6627 [pdf, other]

Title: Minimum d-dimensional arrangement with fixed points

Anupam Gupta, Anastasios Sidiropoulos

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

[70] arXiv:1307.6789 [pdf, other]

Title: Optimal Top-k Document Retrieval

Gonzalo Navarro, Yakov Nekrich

Subjects: Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR)

[71] arXiv:1307.6809 [pdf, other]

Title: A strongly polynomial algorithm for generalized flow maximization

László A. Végh

Comments: minor corrections

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)

[72] arXiv:1307.7089 [pdf, other]

Title: An approximation algorithm for the Bandpass-2 problem

Weitian Tong, Zhi-Zhong Chen, Lusheng Wang, Yinfeng Xu, Jiuping Xu, Randy Goebel, Guohui Lin

Subjects: Data Structures and Algorithms (cs.DS)

[73] arXiv:1307.7259 [pdf, other]

Title: The predecessor-existence problem for k-reversible processes

Leonardo I. L. Oliveira, Valmir C. Barbosa, Fábio Protti

Journal-ref: Theoretical Computer Science 562 (2015), 406-418

Subjects: Data Structures and Algorithms (cs.DS); Cellular Automata and Lattice Gases (nlin.CG)

[74] arXiv:1307.7364 [pdf, other]

Title: On active and passive testing

Noga Alon, Rani Hod, Amit Weinstein

Comments: 16 pages

Journal-ref: Combinator. Probab. Comp. 25 (2016) 1-20

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

[75] arXiv:1307.7430 [pdf, other]

Title: Holographic Algorithms Beyond Matchgates

Jin-Yi Cai, Heng Guo, Tyson Williams

Comments: Inf. Comput., to appear. Author accepted manuscript

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