Data Structures and Algorithms

Authors and titles for July 2013

[76] arXiv:1307.7454 [pdf, other]

Title: Relative Errors for Deterministic Low-Rank Matrix Approximations

Mina Ghashami, Jeff M. Phillips

Comments: 16 pages, 0 figures

Subjects: Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)

[77] arXiv:1307.7806 [pdf, other]

Title: On NP-Hardness of the Paired de Bruijn Sound Cycle Problem

Evgeny Kapun, Fedor Tsarev

Comments: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

Subjects: Data Structures and Algorithms (cs.DS); Quantitative Methods (q-bio.QM)

[78] arXiv:1307.7821 [pdf, other]

Title: Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree

Jesper Jansson, Chuanqi Shen, Wing-Kin Sung

Comments: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

Subjects: Data Structures and Algorithms (cs.DS); Computational Engineering, Finance, and Science (cs.CE); Quantitative Methods (q-bio.QM)

[79] arXiv:1307.7824 [pdf, other]

Title: The generalized Robinson-Foulds metric

Sebastian Böcker, Stefan Canzar, Gunnar W. Klau

Comments: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

Subjects: Data Structures and Algorithms (cs.DS); Computational Engineering, Finance, and Science (cs.CE); Quantitative Methods (q-bio.QM)

[80] arXiv:1307.7842 [pdf, other]

Title: A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications

Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz, Irena Rusu

Comments: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

Subjects: Data Structures and Algorithms (cs.DS); Computational Engineering, Finance, and Science (cs.CE); Quantitative Methods (q-bio.QM)

[81] arXiv:1307.7925 [pdf, other]

Title: Detecting Superbubbles in Assembly Graphs

Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya

Comments: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

Subjects: Data Structures and Algorithms (cs.DS); Computational Engineering, Finance, and Science (cs.CE); Discrete Mathematics (cs.DM); Quantitative Methods (q-bio.QM)

[82] arXiv:1307.8037 [pdf, other]

Title: A Rational Convex Program for Linear Arrow-Debreu Markets

Nikhil R. Devanur, Jugal Garg, László A. Végh

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

[83] arXiv:1307.0099 (cross-list from cs.FL) [pdf, other]

Title: On a compact encoding of the swap automaton

Kimmo Fredriksson, Emanuele Giaquinta

Subjects: Formal Languages and Automata Theory (cs.FL); Data Structures and Algorithms (cs.DS)

[84] arXiv:1307.0441 (cross-list from cs.DB) [pdf, other]

Title: Aggregation and Ordering in Factorised Databases

Nurzhan Bakibayev, Tomáš Kočiský, Dan Olteanu, Jakub Závodný

Comments: 12 pages, 8 figures

Subjects: Databases (cs.DB); Data Structures and Algorithms (cs.DS)

[85] arXiv:1307.0920 (cross-list from cs.IT) [pdf, other]

Title: Domain Specific Hierarchical Huffman Encoding

K.Ilambharathi, G.S.N.V.Venkata Manik, N.Sadagopan, B.Sivaselvan

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

[86] arXiv:1307.1372 (cross-list from cs.NE) [pdf, other]

Title: Clustering of Complex Networks and Community Detection Using Group Search Optimization

G.Kishore Kumar, V.K.Jayaraman

Comments: 7 pages, 2 figures

Subjects: Neural and Evolutionary Computing (cs.NE); Data Structures and Algorithms (cs.DS)

[87] arXiv:1307.2582 (cross-list from math.OC) [pdf, other]

Title: NECO - A scalable algorithm for NEtwork COntrol

Sean P. Cornelius, Adilson E. Motter

Comments: Source codes available at this http URL

Journal-ref: Protocol Exchange (2013) doi:10.1038/protex.2013.063 Published online 27 June 2013

Subjects: Optimization and Control (math.OC); Disordered Systems and Neural Networks (cond-mat.dis-nn); Data Structures and Algorithms (cs.DS); Adaptation and Self-Organizing Systems (nlin.AO); Physics and Society (physics.soc-ph)

[88] arXiv:1307.2908 (cross-list from cs.GT) [pdf, other]

Title: Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations

Haris Aziz, Chun Ye

Comments: 39 pages

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

[89] arXiv:1307.2982 (cross-list from cs.CV) [pdf, other]

Title: Fast Exact Search in Hamming Space with Multi-Index Hashing

Mohammad Norouzi, Ali Punjani, David J. Fleet

Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR)

[90] arXiv:1307.3080 (cross-list from cs.DC) [pdf, other]

Title: Optimal competitiveness for Symmetric Rectilinear Steiner Arborescence and related problems

Erez Kantor, Shay Kutten

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)

[91] arXiv:1307.3102 (cross-list from cs.LG) [pdf, other]

Title: Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy

Maria Florina Balcan, Vitaly Feldman

Comments: Extended abstract appears in NIPS 2013

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

[92] arXiv:1307.3699 (cross-list from cs.CR) [pdf, other]

Title: Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead

Kai-Min Chung, Zhenming Liu, Rafael Pass

Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)

[93] arXiv:1307.3794 (cross-list from cs.GT) [pdf, other]

Title: The Network Improvement Problem for Equilibrium Routing

Umang Bhaskar, Katrina Ligett, Leonard J. Schulman

Comments: 27 pages (including abstract), 3 figures

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

[94] arXiv:1307.3872 (cross-list from cs.IT) [pdf, other]

Title: Bicriteria data compression

Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, Rossano Venturini

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

[95] arXiv:1307.4258 (cross-list from cs.GT) [pdf, other]

Title: Complexity and Approximation of the Continuous Network Design Problem

Martin Gairing, Tobias Harks, Max Klimm

Comments: 27 pages

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

[96] arXiv:1307.4334 (cross-list from math.OC) [pdf, other]

Title: A polynomial projection-type algorithm for linear programming

László A. Végh, Giacomo Zambelli

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

[97] arXiv:1307.4420 (cross-list from cs.CC) [pdf, other]

Title: On the Complexity of a Matching Problem with Asymmetric Weights

Lily Briggs

Comments: 9 pages; v2 fixed typos, made minor clarifications, and added author affiliation

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

[98] arXiv:1307.5230 (cross-list from cs.NI) [pdf, other]

Title: Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks

Vivek Kumar Bagaria, Ashwin Pananjady, Rahul Vaze

Comments: submitted to IEEE/ACM Transactions on Networking, 17 pages

Subjects: Networking and Internet Architecture (cs.NI); Data Structures and Algorithms (cs.DS)

[99] arXiv:1307.5519 (cross-list from cs.NE) [pdf, other]

Title: Optimal Recombination in Genetic Algorithms

Anton V. Eremeev, Julia V. Kovalenko

Subjects: Neural and Evolutionary Computing (cs.NE); Data Structures and Algorithms (cs.DS)

[100] arXiv:1307.5674 (cross-list from cs.NE) [pdf, other]

Title: Solving Traveling Salesman Problem by Marker Method

Masoumeh Vali

Subjects: Neural and Evolutionary Computing (cs.NE); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)