for Journals by Title or ISSN
for Articles by Keywords
help
  Subjects -> COMPUTER SCIENCE (Total: 1969 journals)
    - ANIMATION AND SIMULATION (29 journals)
    - ARTIFICIAL INTELLIGENCE (97 journals)
    - AUTOMATION AND ROBOTICS (96 journals)
    - CLOUD COMPUTING AND NETWORKS (62 journals)
    - COMPUTER ARCHITECTURE (9 journals)
    - COMPUTER ENGINEERING (10 journals)
    - COMPUTER GAMES (15 journals)
    - COMPUTER PROGRAMMING (23 journals)
    - COMPUTER SCIENCE (1147 journals)
    - COMPUTER SECURITY (45 journals)
    - DATA BASE MANAGEMENT (12 journals)
    - DATA MINING (32 journals)
    - E-BUSINESS (22 journals)
    - E-LEARNING (28 journals)
    - ELECTRONIC DATA PROCESSING (21 journals)
    - IMAGE AND VIDEO PROCESSING (40 journals)
    - INFORMATION SYSTEMS (101 journals)
    - INTERNET (91 journals)
    - SOCIAL WEB (49 journals)
    - SOFTWARE (32 journals)
    - THEORY OF COMPUTING (8 journals)

COMPUTER SCIENCE (1147 journals)                  1 2 3 4 5 6 | Last

Showing 1 - 200 of 872 Journals sorted alphabetically
3D Printing and Additive Manufacturing     Full-text available via subscription   (Followers: 11)
Abakós     Open Access   (Followers: 3)
Academy of Information and Management Sciences Journal     Full-text available via subscription   (Followers: 67)
ACM Computing Surveys     Hybrid Journal   (Followers: 23)
ACM Journal on Computing and Cultural Heritage     Hybrid Journal   (Followers: 8)
ACM Journal on Emerging Technologies in Computing Systems     Hybrid Journal   (Followers: 13)
ACM Transactions on Accessible Computing (TACCESS)     Hybrid Journal   (Followers: 4)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 16)
ACM Transactions on Applied Perception (TAP)     Hybrid Journal   (Followers: 6)
ACM Transactions on Architecture and Code Optimization (TACO)     Hybrid Journal   (Followers: 9)
ACM Transactions on Autonomous and Adaptive Systems (TAAS)     Hybrid Journal   (Followers: 7)
ACM Transactions on Computation Theory (TOCT)     Hybrid Journal   (Followers: 11)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 4)
ACM Transactions on Computer Systems (TOCS)     Hybrid Journal   (Followers: 18)
ACM Transactions on Computer-Human Interaction     Hybrid Journal   (Followers: 12)
ACM Transactions on Computing Education (TOCE)     Hybrid Journal   (Followers: 3)
ACM Transactions on Design Automation of Electronic Systems (TODAES)     Hybrid Journal   (Followers: 1)
ACM Transactions on Economics and Computation     Hybrid Journal  
ACM Transactions on Embedded Computing Systems (TECS)     Hybrid Journal   (Followers: 4)
ACM Transactions on Information Systems (TOIS)     Hybrid Journal   (Followers: 19)
ACM Transactions on Intelligent Systems and Technology (TIST)     Hybrid Journal   (Followers: 9)
ACM Transactions on Interactive Intelligent Systems (TiiS)     Hybrid Journal   (Followers: 4)
ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP)     Hybrid Journal   (Followers: 10)
ACM Transactions on Reconfigurable Technology and Systems (TRETS)     Hybrid Journal   (Followers: 7)
ACM Transactions on Sensor Networks (TOSN)     Hybrid Journal   (Followers: 8)
ACM Transactions on Speech and Language Processing (TSLP)     Hybrid Journal   (Followers: 10)
ACM Transactions on Storage     Hybrid Journal  
ACS Applied Materials & Interfaces     Full-text available via subscription   (Followers: 21)
Acta Automatica Sinica     Full-text available via subscription   (Followers: 3)
Acta Universitatis Cibiniensis. Technical Series     Open Access  
Ad Hoc Networks     Hybrid Journal   (Followers: 11)
Adaptive Behavior     Hybrid Journal   (Followers: 10)
Advanced Engineering Materials     Hybrid Journal   (Followers: 24)
Advanced Science Letters     Full-text available via subscription   (Followers: 5)
Advances in Adaptive Data Analysis     Hybrid Journal   (Followers: 8)
Advances in Artificial Intelligence     Open Access   (Followers: 14)
Advances in Artificial Neural Systems     Open Access   (Followers: 4)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 2)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15)
Advances in Computer Science : an International Journal     Open Access   (Followers: 13)
Advances in Computing     Open Access   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 53)
Advances in Engineering Software     Hybrid Journal   (Followers: 25)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 9)
Advances in Human Factors/Ergonomics     Full-text available via subscription   (Followers: 23)
Advances in Human-Computer Interaction     Open Access   (Followers: 19)
Advances in Materials Sciences     Open Access   (Followers: 16)
Advances in Operations Research     Open Access   (Followers: 11)
Advances in Parallel Computing     Full-text available via subscription   (Followers: 7)
Advances in Porous Media     Full-text available via subscription   (Followers: 4)
Advances in Remote Sensing     Open Access   (Followers: 35)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Advances in Technology Innovation     Open Access  
AEU - International Journal of Electronics and Communications     Hybrid Journal   (Followers: 8)
African Journal of Information and Communication     Open Access   (Followers: 6)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 4)
Air, Soil & Water Research     Open Access   (Followers: 7)
AIS Transactions on Human-Computer Interaction     Open Access   (Followers: 6)
Algebras and Representation Theory     Hybrid Journal   (Followers: 1)
Algorithms     Open Access   (Followers: 9)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 3)
American Journal of Computational Mathematics     Open Access   (Followers: 4)
American Journal of Information Systems     Open Access   (Followers: 6)
American Journal of Sensor Technology     Open Access   (Followers: 2)
Anais da Academia Brasileira de Ciências     Open Access   (Followers: 2)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 5)
Analysis in Theory and Applications     Hybrid Journal  
Animation Practice, Process & Production     Hybrid Journal   (Followers: 5)
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Data Science     Hybrid Journal   (Followers: 8)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 6)
Annals of Pure and Applied Logic     Open Access   (Followers: 2)
Annals of Software Engineering     Hybrid Journal   (Followers: 12)
Annual Reviews in Control     Hybrid Journal   (Followers: 6)
Anuario Americanista Europeo     Open Access  
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applied and Computational Harmonic Analysis     Full-text available via subscription   (Followers: 2)
Applied Artificial Intelligence: An International Journal     Hybrid Journal   (Followers: 13)
Applied Categorical Structures     Hybrid Journal   (Followers: 2)
Applied Clinical Informatics     Hybrid Journal   (Followers: 1)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 12)
Applied Computer Systems     Open Access   (Followers: 1)
Applied Informatics     Open Access  
Applied Mathematics and Computation     Hybrid Journal   (Followers: 31)
Applied Medical Informatics     Open Access   (Followers: 9)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Soft Computing     Hybrid Journal   (Followers: 16)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4)
Architectural Theory Review     Hybrid Journal   (Followers: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4)
Artifact     Hybrid Journal   (Followers: 2)
Artificial Life     Hybrid Journal   (Followers: 5)
Asia Pacific Journal on Computational Engineering     Open Access  
Asia-Pacific Journal of Information Technology and Multimedia     Open Access   (Followers: 1)
Asian Journal of Computer Science and Information Technology     Open Access  
Asian Journal of Control     Hybrid Journal  
Assembly Automation     Hybrid Journal   (Followers: 2)
at - Automatisierungstechnik     Hybrid Journal   (Followers: 1)
Australian Educational Computing     Open Access  
Automatic Control and Computer Sciences     Hybrid Journal   (Followers: 3)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Automatica     Hybrid Journal   (Followers: 8)
Automation in Construction     Hybrid Journal   (Followers: 6)
Autonomous Mental Development, IEEE Transactions on     Hybrid Journal   (Followers: 7)
Basin Research     Hybrid Journal   (Followers: 3)
Behaviour & Information Technology     Hybrid Journal   (Followers: 52)
Bioinformatics     Hybrid Journal   (Followers: 232)
Biomedical Engineering     Hybrid Journal   (Followers: 16)
Biomedical Engineering and Computational Biology     Open Access   (Followers: 13)
Biomedical Engineering, IEEE Reviews in     Full-text available via subscription   (Followers: 16)
Biomedical Engineering, IEEE Transactions on     Hybrid Journal   (Followers: 31)
Briefings in Bioinformatics     Hybrid Journal   (Followers: 45)
British Journal of Educational Technology     Hybrid Journal   (Followers: 118)
Broadcasting, IEEE Transactions on     Hybrid Journal   (Followers: 10)
c't Magazin fuer Computertechnik     Full-text available via subscription   (Followers: 1)
CALCOLO     Hybrid Journal  
Calphad     Hybrid Journal  
Canadian Journal of Electrical and Computer Engineering     Full-text available via subscription   (Followers: 12)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal  
Cell Communication and Signaling     Open Access   (Followers: 1)
Central European Journal of Computer Science     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
Chemometrics and Intelligent Laboratory Systems     Hybrid Journal   (Followers: 15)
ChemSusChem     Hybrid Journal   (Followers: 7)
China Communications     Full-text available via subscription   (Followers: 7)
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
CIN Computers Informatics Nursing     Full-text available via subscription   (Followers: 12)
Circuits and Systems     Open Access   (Followers: 13)
Clean Air Journal     Full-text available via subscription   (Followers: 2)
CLEI Electronic Journal     Open Access  
Clin-Alert     Hybrid Journal   (Followers: 1)
Cluster Computing     Hybrid Journal   (Followers: 1)
Cognitive Computation     Hybrid Journal   (Followers: 4)
COMBINATORICA     Hybrid Journal  
Combustion Theory and Modelling     Hybrid Journal   (Followers: 13)
Communication Methods and Measures     Hybrid Journal   (Followers: 11)
Communication Theory     Hybrid Journal   (Followers: 18)
Communications Engineer     Hybrid Journal   (Followers: 1)
Communications in Algebra     Hybrid Journal   (Followers: 3)
Communications in Partial Differential Equations     Hybrid Journal   (Followers: 3)
Communications of the ACM     Full-text available via subscription   (Followers: 47)
Communications of the Association for Information Systems     Open Access   (Followers: 18)
COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering     Hybrid Journal   (Followers: 3)
Complex & Intelligent Systems     Open Access  
Complex Adaptive Systems Modeling     Open Access  
Complex Analysis and Operator Theory     Hybrid Journal   (Followers: 2)
Complexity     Hybrid Journal   (Followers: 6)
Complexus     Full-text available via subscription  
Composite Materials Series     Full-text available via subscription   (Followers: 9)
Computación y Sistemas     Open Access  
Computation     Open Access  
Computational and Applied Mathematics     Hybrid Journal   (Followers: 2)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational and Structural Biotechnology Journal     Open Access   (Followers: 2)
Computational and Theoretical Chemistry     Hybrid Journal   (Followers: 9)
Computational Astrophysics and Cosmology     Open Access  
Computational Biology and Chemistry     Hybrid Journal   (Followers: 12)
Computational Chemistry     Open Access   (Followers: 2)
Computational Cognitive Science     Open Access   (Followers: 1)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Condensed Matter     Open Access  
Computational Ecology and Software     Open Access   (Followers: 8)
Computational Economics     Hybrid Journal   (Followers: 9)
Computational Geosciences     Hybrid Journal   (Followers: 12)
Computational Linguistics     Open Access   (Followers: 23)
Computational Management Science     Hybrid Journal  
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 4)
Computational Methods and Function Theory     Hybrid Journal  
Computational Molecular Bioscience     Open Access   (Followers: 2)
Computational Optimization and Applications     Hybrid Journal   (Followers: 7)
Computational Particle Mechanics     Hybrid Journal   (Followers: 1)
Computational Research     Open Access   (Followers: 1)
Computational Science and Discovery     Full-text available via subscription   (Followers: 2)
Computational Science and Techniques     Open Access  
Computational Statistics     Hybrid Journal   (Followers: 13)
Computational Statistics & Data Analysis     Hybrid Journal   (Followers: 27)
Computer     Full-text available via subscription   (Followers: 78)
Computer Aided Surgery     Hybrid Journal   (Followers: 3)
Computer Applications in Engineering Education     Hybrid Journal   (Followers: 6)
Computer Communications     Hybrid Journal   (Followers: 10)
Computer Engineering and Applications Journal     Open Access   (Followers: 5)
Computer Journal     Hybrid Journal   (Followers: 8)
Computer Methods in Applied Mechanics and Engineering     Hybrid Journal   (Followers: 22)
Computer Methods in Biomechanics and Biomedical Engineering     Hybrid Journal   (Followers: 10)
Computer Methods in the Geosciences     Full-text available via subscription   (Followers: 1)
Computer Music Journal     Hybrid Journal   (Followers: 13)
Computer Physics Communications     Hybrid Journal   (Followers: 6)
Computer Science - Research and Development     Hybrid Journal   (Followers: 7)
Computer Science and Engineering     Open Access   (Followers: 17)
Computer Science and Information Technology     Open Access   (Followers: 10)
Computer Science Education     Hybrid Journal   (Followers: 12)
Computer Science Journal     Open Access   (Followers: 20)
Computer Science Master Research     Open Access   (Followers: 9)
Computer Science Review     Hybrid Journal   (Followers: 10)

        1 2 3 4 5 6 | Last

Journal Cover ACM Transactions on Algorithms (TALG)
  [SJR: 1.796]   [H-I: 30]   [16 followers]  Follow
    
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 1549-6325 - ISSN (Online) 1549-6333
   Published by ACM Homepage  [45 journals]
  • Combinatorial Algorithm for Restricted Max-Min Fair Allocation
    • Abstract: Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson

      We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ ϵ. In contrast, however, the best-known approximation algorithm for the problem has an unspecified large constant guarantee. In this article, we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [13] for hypergraph matchings and later used in this context by Asadpour, Feige, and Saberi [2].
      PubDate: Fri, 26 May 2017 00:00:00 GMT
       
  • Cost-Oblivious Storage Reallocation
    • Abstract: Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

      Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests. This article defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated, but at some cost. This cost is determined by the allocation/reallocation cost function.
      PubDate: Fri, 26 May 2017 00:00:00 GMT
       
  • Maximizing Symmetric Submodular Functions
    • Abstract: Moran Feldman

      Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by current research, unlike similar minimization problems that have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state-of-the-art approximation for general submodular functions. We first consider the problem of maximizing a non-negative symmetric submodular function f:2N → R+ subject to a down-monotone solvable polytope P ⊆ [0, 1]N. For this problem, we describe an algorithm producing a fractional solution of value at least 0.432 ċ f(OPT), where OPT is the optimal integral solution.
      PubDate: Fri, 26 May 2017 00:00:00 GMT
       
  • Editorial
    • Abstract: Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk


      PubDate: Tue, 21 Mar 2017 00:00:00 GMT
       
  • Smoothed Analysis of Local Search for the Maximum-Cut Problem
    • Abstract: Michael Etscheid, Heiko Röglin

      Even though local search heuristics are the method of choice in practice for many well-studied optimization problems, most of them behave poorly in the worst case. This is, in particular, the case for the Maximum-Cut Problem, for which local search can take an exponential number of steps to terminate and the problem of computing a local optimum is PLS-complete. To narrow the gap between theory and practice, we study local search for the Maximum-Cut Problem in the framework of smoothed analysis in which inputs are subject to a small amount of random noise. We show that the smoothed number of iterations is quasi-polynomial, that is, it is bounded from above by a polynomial in nlog n and φ, where n denotes the number of nodes and φ denotes the perturbation parameter.
      PubDate: Tue, 21 Mar 2017 00:00:00 GMT
       
  • Uniform Kernelization Complexity of Hitting Forbidden Minors
    • Abstract: Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh

      The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. At FOCS 2012, Fomin et al. showed that the special case when F contains at least one planar graph has a kernel of size f(F) ċ kg(F) for some functions f and g. They left open whether this Planar F-Minor-Free Deletion problem has kernels whose size is uniformly polynomial, of the form f(F) ċ kc for some universal constant c.
      PubDate: Mon, 20 Mar 2017 00:00:00 GMT
       
  • Representative Families of Product Families
    • Abstract: Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

      A subfamily F′ of a set family F is said to q-represent F if for every A ∈ F and B of size q such that A∩B = ∅ there exists a set A′ ∈ F′ such that A′ ∩ B = ∅. Recently, we provided an algorithm that, for a given family F of sets of size p together with an integer q, efficiently computes a q-representative family F′ of F of size approximately (p+q&atop;p). In this article, we consider the efficient computation of q-representative families for product families F. A family F is a product family if there exist families A and B such that F = { A, &cup, B : A ∈ A, B ∈ B, A, &cap, B = ∅}.
      PubDate: Mon, 13 Mar 2017 00:00:00 GMT
       
  • Property Testing on Product Distributions: Optimal Testers for Bounded
           Derivative Properties
    • Abstract: Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

      The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges.
      PubDate: Fri, 10 Mar 2017 00:00:00 GMT
       
  • A Fast and Simple Surface Reconstruction Algorithm
    • Abstract: Siu-Wing Cheng, Jiongxin Jin, Man-Kit Lau

      We present an algorithm for surface reconstruction from a point cloud. It runs in O(nlog n) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O(nlog n)-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task is to extract a locally uniform subsample from the input points. Our algorithm is much simpler and it is based on a variant of the standard octree. We built a prototype that runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the sample points absent from the subsample via edge flips.
      PubDate: Fri, 10 Mar 2017 00:00:00 GMT
       
  • ACM Transactions on Algorithms (TALG) Volume 13 Issue 3, March 2017
           (Issue-in-Progress)
    • PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Faster and Simpler Sketches of Valuation Functions
    • Abstract: Keren Cohavi, Shahar Dobzinski

      We present fast algorithms for sketching valuation functions. Let N (|N| = n) be some ground set and v:2N→ R be a function. We say that &vtilde;:2N→ R is an α-sketch of v if for every set S we have that v(S)/α ≤ &vtilde;(S) ≤ v(S) and &vtilde; can be described in poly(n) bits. Goemans et al. [SODA’09] showed that if v is submodular then there exists an õ(&sqrt;n)-sketch that can be constructed using polynomially many value queries (this is essentially the best possible, as Balcan and Harvey [STOC’11] show that no submodular function admits an n1/3 - ε-sketch). Based on their work, Balcan et al.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
    • Abstract: Christian Glacet, Avery Miller, Andrzej Pelc

      Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • For-All Sparse Recovery in Near-Optimal Time
    • Abstract: Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

      An approximate sparse recovery system in ℓ1 norm consists of parameters k, ε, N; an m-by-N measurement Φ; and a recovery algorithm R. Given a vector, x, the system approximates x by &xwidehat; = R(Φ x), which must satisfy ‖ &xwidehat;-x‖1 ≤ (1+ε)‖ x - xk‖1. We consider the “for all” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x. The best existing sublinear algorithm by Porat and Strauss [2012] uses O(ε−3klog (N/k)) measurements and runs in time O(k1 − αNα) for any constant α > 0. In this article, we improve the number of measurements to O(ε − 2klog (N/k)), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O(k1+βpoly(log N,1/ε)), with a modest restriction that k ⩽ N1 − α and ε ⩽ (log k/log N)γ for any constants α, β, γ ...
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution
    • Abstract: David G. Harris, Aravind Srinivasan

      Moser and Tardos have developed a powerful algorithmic approach (henceforth MT) to the Lovász Local Lemma (LLL); the basic operation done in MT and its variants is a search for “bad” events in a current configuration. In the initial stage of MT, the variables are set independently. We examine the distributions on these variables that arise during intermediate stages of MT. We show that these configurations have a more or less “random” form, building further on the MT-distribution concept of Haeupler et al. in understanding the (intermediate and) output distribution of MT. This has a variety of algorithmic applications; the most important is that bad events can be found relatively quickly, improving on MT across the complexity spectrum.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
    • Abstract: Mahdi Cheraghchi, Piotr Indyk

      For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x ∈ RN in time k1 + α(log N)O(1). Specifically, the algorithm is given query access to x and computes a k-sparse &xtilde; ∈ RN satisfying ‖ &xtilde;− &xhat;‖1 ≤ c ‖ &xhat;− Hk(&xhat)‖‖1 for an absolute constant c > 0, where &xhat; is the transform of x and Hk(&xhat) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses nonadaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts).
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • An Improved Approximation for k-Median and Positive Correlation in
           Budgeted Optimization
    • Abstract: Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh

      Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding but also have nearly bestpossible behavior—near-independence, which generalizes positive correlation—on “small” subsets of the variables. The recent breakthrough of Li and Svensson for the classical k-median problem has to handle positive correlation in certain dependent rounding settings, and does so implicitly. We improve upon Li-Svensson’s approximation ratio for k-median from 2.732 + ε to 2.675 + ε by developing an algorithm that improves upon various aspects of their work.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices,
           and Their Applications
    • Abstract: Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir

      We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O(nlog n) space and O(nlogn) preprocessing time, and answers queries in O(log2n) time. For partial Monge matrices, the space grows by α(n), the preprocessing grows by α(n)logn (α(n) is the inverse Ackermann function), and the query remains O(log2n). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively).
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Asymptotically Optimal Encodings of Range Data Structures for Selection
           and Top-k Queries
    • Abstract: Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, S. Rao Satti

      Given an array A[1, n] of elements with a total order, we consider the problem of building a data structure that solves two queries: (a) selection queries receive a range [i, j] and an integer k and return the position of the kth largest element in A[i, j]; (b) top-k queries receive [i, j] and k and return the positions of the k largest elements in A[i, j]. These problems can be solved in optimal time, O(1+lg k/lg lg n) and O(k), respectively, using linear-space data structures. We provide the first study of the encoding data structures for the above problems, where A cannot be accessed at query time.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Discovering Archipelagos of Tractability for Constraint Satisfaction and
           Counting
    • Abstract: Robert Ganian, M. S. Ramanujan, Stefan Szeider

      The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called “islands of tractability.” A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language, whereas a constraint language is conservative if it contains all unary relations. Schaefer’s famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values.
      PubDate: Mon, 06 Mar 2017 00:00:00 GMT
       
  • Dynamic Facility Location via Exponential Clocks
    • Abstract: Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson

      The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the “stability” of the solution: There is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches.
      PubDate: Tue, 07 Feb 2017 00:00:00 GMT
       
  • Generating Random Permutations by Coin Tossing: Classical Algorithms, New
           Analysis, and Modern Implementation
    • Abstract: Axel Bacher, Olivier Bodini, Hsien-Kuei Hwang, Tsung-Hsi Tsai

      Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given.
      PubDate: Tue, 07 Feb 2017 00:00:00 GMT
       
  • ACM Transactions on Algorithms (TALG) Volume 13 Issue 2, January 2017
           (Issue-in-Progress)
    • PubDate: Sat, 14 Jan 2017 00:00:00 GMT
       
  • On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
    • Abstract: Shi Li

      In this article, we study the uniform capacitated k-median (CKM) problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C, an upper bound k on the number of facilities that we can open, and an upper bound u on the number of clients that each facility can serve. We need to open a subset S ⊆ F of k facilities and connect clients in C to facilities in S so that each facility is connected by at most u clients. The goal is to minimize the total connection cost over all clients.
      PubDate: Sat, 14 Jan 2017 00:00:00 GMT
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.196.107.247
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016