for Journals by Title or ISSN
for Articles by Keywords
  Subjects -> MATHEMATICS (Total: 978 journals)
    - APPLIED MATHEMATICS (81 journals)
    - GEOMETRY AND TOPOLOGY (20 journals)
    - MATHEMATICS (723 journals)
    - MATHEMATICS (GENERAL) (41 journals)
    - NUMERICAL ANALYSIS (22 journals)

MATHEMATICS (723 journals)                  1 2 3 4 | Last

Showing 1 - 200 of 538 Journals sorted alphabetically
Abakós     Open Access   (Followers: 4)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 4)
Academic Voices : A Multidisciplinary Journal     Open Access   (Followers: 2)
Accounting Perspectives     Full-text available via subscription   (Followers: 7)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 15)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 3)
ACM Transactions on Mathematical Software (TOMS)     Hybrid Journal   (Followers: 6)
ACS Applied Materials & Interfaces     Hybrid Journal   (Followers: 32)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1)
Acta Mathematica     Hybrid Journal   (Followers: 12)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2)
Acta Mathematica Scientia     Full-text available via subscription   (Followers: 5)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 6)
Acta Mathematica Vietnamica     Hybrid Journal  
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal  
Advanced Science Letters     Full-text available via subscription   (Followers: 10)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 4)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 4)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Complex Systems     Hybrid Journal   (Followers: 7)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 19)
Advances in Decision Sciences     Open Access   (Followers: 3)
Advances in Difference Equations     Open Access   (Followers: 3)
Advances in Fixed Point Theory     Open Access   (Followers: 5)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 14)
Advances in Linear Algebra & Matrix Theory     Open Access   (Followers: 3)
Advances in Materials Science     Open Access   (Followers: 14)
Advances in Mathematical Physics     Open Access   (Followers: 4)
Advances in Mathematics     Full-text available via subscription   (Followers: 11)
Advances in Nonlinear Analysis     Hybrid Journal  
Advances in Numerical Analysis     Open Access   (Followers: 5)
Advances in Operations Research     Open Access   (Followers: 12)
Advances in Porous Media     Full-text available via subscription   (Followers: 5)
Advances in Pure and Applied Mathematics     Hybrid Journal   (Followers: 6)
Advances in Pure Mathematics     Open Access   (Followers: 6)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2)
African Journal of Educational Studies in Mathematics and Sciences     Full-text available via subscription   (Followers: 5)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 4)
Afrika Matematika     Hybrid Journal   (Followers: 1)
Air, Soil & Water Research     Open Access   (Followers: 12)
AKSIOMA Journal of Mathematics Education     Open Access   (Followers: 1)
Al-Jabar : Jurnal Pendidikan Matematika     Open Access   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 6)
Algebra Colloquium     Hybrid Journal   (Followers: 4)
Algebra Universalis     Hybrid Journal   (Followers: 2)
Algorithmic Operations Research     Full-text available via subscription   (Followers: 5)
Algorithms     Open Access   (Followers: 11)
Algorithms Research     Open Access   (Followers: 1)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 5)
American Journal of Mathematical Analysis     Open Access  
American Journal of Mathematics     Full-text available via subscription   (Followers: 6)
American Journal of Operations Research     Open Access   (Followers: 5)
An International Journal of Optimization and Control: Theories & Applications     Open Access   (Followers: 9)
Analele Universitatii Ovidius Constanta - Seria Matematica     Open Access   (Followers: 1)
Analysis and Applications     Hybrid Journal   (Followers: 1)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 5)
Analysis Mathematica     Full-text available via subscription  
Analysis. International mathematical journal of analysis and its applications     Hybrid Journal   (Followers: 2)
Annales Mathematicae Silesianae     Open Access  
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica     Open Access  
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1)
Annals of Combinatorics     Hybrid Journal   (Followers: 4)
Annals of Data Science     Hybrid Journal   (Followers: 12)
Annals of Discrete Mathematics     Full-text available via subscription   (Followers: 6)
Annals of Mathematics     Full-text available via subscription   (Followers: 1)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 13)
Annals of Pure and Applied Logic     Open Access   (Followers: 3)
Annals of the Alexandru Ioan Cuza University - Mathematics     Open Access  
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1)
Annals of West University of Timisoara - Mathematics     Open Access  
Annuaire du Collège de France     Open Access   (Followers: 5)
ANZIAM Journal     Open Access   (Followers: 1)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applications of Mathematics     Hybrid Journal   (Followers: 2)
Applied Categorical Structures     Hybrid Journal   (Followers: 2)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 13)
Applied Mathematics     Open Access   (Followers: 3)
Applied Mathematics     Open Access   (Followers: 7)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 9)
Applied Mathematics - A Journal of Chinese Universities     Hybrid Journal  
Applied Mathematics Letters     Full-text available via subscription   (Followers: 2)
Applied Mathematics Research eXpress     Hybrid Journal   (Followers: 1)
Applied Network Science     Open Access   (Followers: 3)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5)
Arab Journal of Mathematical Sciences     Open Access   (Followers: 3)
Arabian Journal of Mathematics     Open Access   (Followers: 2)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 5)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 5)
Arkiv för Matematik     Hybrid Journal   (Followers: 1)
Armenian Journal of Mathematics     Open Access  
Arnold Mathematical Journal     Hybrid Journal   (Followers: 1)
Artificial Satellites     Open Access   (Followers: 21)
Asia-Pacific Journal of Operational Research     Hybrid Journal   (Followers: 3)
Asian Journal of Algebra     Open Access   (Followers: 1)
Asian Journal of Current Engineering & Maths     Open Access  
Asian-European Journal of Mathematics     Hybrid Journal   (Followers: 2)
Australian Mathematics Teacher, The     Full-text available via subscription   (Followers: 6)
Australian Primary Mathematics Classroom     Full-text available via subscription   (Followers: 4)
Australian Senior Mathematics Journal     Full-text available via subscription   (Followers: 1)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Axioms     Open Access   (Followers: 1)
Baltic International Yearbook of Cognition, Logic and Communication     Open Access   (Followers: 1)
Basin Research     Hybrid Journal   (Followers: 5)
BIBECHANA     Open Access   (Followers: 2)
Biomath     Open Access  
BIT Numerical Mathematics     Hybrid Journal  
BoEM - Boletim online de Educação Matemática     Open Access  
Boletim Cearense de Educação e História da Matemática     Open Access  
Boletim de Educação Matemática     Open Access  
Boletín de la Sociedad Matemática Mexicana     Hybrid Journal  
Bollettino dell'Unione Matematica Italiana     Full-text available via subscription   (Followers: 1)
British Journal of Mathematical and Statistical Psychology     Full-text available via subscription   (Followers: 20)
Bruno Pini Mathematical Analysis Seminar     Open Access  
Buletinul Academiei de Stiinte a Republicii Moldova. Matematica     Open Access   (Followers: 12)
Bulletin des Sciences Mathamatiques     Full-text available via subscription   (Followers: 4)
Bulletin of Dnipropetrovsk University. Series : Communications in Mathematical Modeling and Differential Equations Theory     Open Access   (Followers: 1)
Bulletin of Mathematical Sciences     Open Access   (Followers: 1)
Bulletin of Symbolic Logic     Full-text available via subscription   (Followers: 2)
Bulletin of the Australian Mathematical Society     Full-text available via subscription   (Followers: 1)
Bulletin of the Brazilian Mathematical Society, New Series     Hybrid Journal  
Bulletin of the London Mathematical Society     Hybrid Journal   (Followers: 4)
Bulletin of the Malaysian Mathematical Sciences Society     Hybrid Journal  
Calculus of Variations and Partial Differential Equations     Hybrid Journal  
Canadian Journal of Science, Mathematics and Technology Education     Hybrid Journal   (Followers: 19)
Carpathian Mathematical Publications     Open Access   (Followers: 1)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal   (Followers: 2)
CHANCE     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
ChemSusChem     Hybrid Journal   (Followers: 7)
Chinese Annals of Mathematics, Series B     Hybrid Journal  
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chinese Journal of Mathematics     Open Access  
Clean Air Journal     Full-text available via subscription   (Followers: 1)
Cogent Mathematics     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 4)
Collectanea Mathematica     Hybrid Journal  
COMBINATORICA     Hybrid Journal  
Combinatorics, Probability and Computing     Hybrid Journal   (Followers: 4)
Combustion Theory and Modelling     Hybrid Journal   (Followers: 14)
Commentarii Mathematici Helvetici     Hybrid Journal   (Followers: 1)
Communications in Combinatorics and Optimization     Open Access  
Communications in Contemporary Mathematics     Hybrid Journal  
Communications in Mathematical Physics     Hybrid Journal   (Followers: 2)
Communications On Pure & Applied Mathematics     Hybrid Journal   (Followers: 3)
Complex Analysis and its Synergies     Open Access   (Followers: 2)
Complex Variables and Elliptic Equations: An International Journal     Hybrid Journal  
Complexus     Full-text available via subscription  
Composite Materials Series     Full-text available via subscription   (Followers: 8)
Compositio Mathematica     Full-text available via subscription   (Followers: 1)
Comptes Rendus Mathematique     Full-text available via subscription   (Followers: 1)
Computational and Applied Mathematics     Hybrid Journal   (Followers: 3)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 5)
Computational Methods and Function Theory     Hybrid Journal  
Computational Optimization and Applications     Hybrid Journal   (Followers: 8)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 8)
Concrete Operators     Open Access   (Followers: 5)
Confluentes Mathematici     Hybrid Journal  
Contributions to Game Theory and Management     Open Access  
COSMOS     Hybrid Journal  
Cryptography and Communications     Hybrid Journal   (Followers: 13)
Cuadernos de Investigación y Formación en Educación Matemática     Open Access  
Cubo. A Mathematical Journal     Open Access  
Current Research in Biostatistics     Open Access   (Followers: 9)
Czechoslovak Mathematical Journal     Hybrid Journal   (Followers: 1)
Demographic Research     Open Access   (Followers: 11)
Demonstratio Mathematica     Open Access  
Dependence Modeling     Open Access  
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 30)
Developments in Clay Science     Full-text available via subscription   (Followers: 1)
Developments in Mineral Processing     Full-text available via subscription   (Followers: 3)
Dhaka University Journal of Science     Open Access  
Differential Equations and Dynamical Systems     Hybrid Journal   (Followers: 3)
Differentsial'nye Uravneniya     Open Access  
Discrete Mathematics     Hybrid Journal   (Followers: 8)
Discrete Mathematics & Theoretical Computer Science     Open Access  
Discrete Mathematics, Algorithms and Applications     Hybrid Journal   (Followers: 2)
Discussiones Mathematicae - General Algebra and Applications     Open Access  
Discussiones Mathematicae Graph Theory     Open Access   (Followers: 1)
Diskretnaya Matematika     Full-text available via subscription  
Dnipropetrovsk University Mathematics Bulletin     Open Access  
Doklady Akademii Nauk     Open Access  
Doklady Mathematics     Hybrid Journal  
Duke Mathematical Journal     Full-text available via subscription   (Followers: 1)
Eco Matemático     Open Access  
Econometrics     Open Access  
Edited Series on Advances in Nonlinear Science and Complexity     Full-text available via subscription  
Electronic Journal of Combinatorics     Open Access  
Electronic Journal of Differential Equations     Open Access  
Electronic Journal of Graph Theory and Applications     Open Access   (Followers: 2)
Electronic Notes in Discrete Mathematics     Full-text available via subscription   (Followers: 2)

        1 2 3 4 | Last

Journal Cover
ACM Transactions on Algorithms (TALG)
Journal Prestige (SJR): 0.804
Citation Impact (citeScore): 2
Number of Followers: 15  
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1549-6325 - ISSN (Online) 1549-6333
Published by ACM Homepage  [45 journals]
  • Entropy and Optimal Compression of Some General Plane Trees
    • Abstract: Zbigniew Gołębiewski, Abram Magner, Wojciech Szpankowski

      We continue developing the information theory of structured data. In this article, we study models generating d-ary trees (d ≥ 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O(nd) elementary arithmetic operations (each corresponding to a number f(n, d) of bit operations), but our efficient algorithms run in O(n2) of these operations, where n is the number of nodes.
      PubDate: Mon, 01 Oct 2018 00:00:00 GMT
  • Stream Sampling Framework and Application for Frequency Cap Statistics
    • Abstract: Edith Cohen

      Unaggregated data, in a streamed or distributed form, are prevalent and come from diverse sources such as interactions of users with web services and IP traffic. Data elements have keys (cookies, users, queries), and elements with different keys interleave. Analytics on such data typically utilizes statistics expressed as a sum over keys in a specified segment of a function f applied to the frequency (the total number of occurrences) of the key. In particular, Distinct is the number of active keys in the segment, Sum is the sum of their frequencies, and both are special cases of frequency cap statistics, which cap the frequency by a parameter T.
      PubDate: Mon, 24 Sep 2018 00:00:00 GMT
  • ACM Transactions on Algorithms (TALG) Volume 15 Issue 1, September 2018
    • PubDate: Mon, 24 Sep 2018 00:00:00 GMT
  • Distribution-free Junta Testing
    • Abstract: Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie

      We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}n. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ(k2)/ε queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy ε = 1/3.
      PubDate: Mon, 24 Sep 2018 00:00:00 GMT
  • Network Sparsification for Steiner Problems on Planar and Bounded-Genus
    • Abstract: Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan Van Leeuwen

      We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F ⊆ E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and E(T) .
      PubDate: Mon, 17 Sep 2018 00:00:00 GMT
  • Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
    • Abstract: Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter

      Given a planar graph G and a partition of the neighbors of each vertex v in four sets v↗, v↖, v↙, and v↘, the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∈ v↗v is above and to the right of v, (ii) each neighbor u ∈ v↖ is above and to the left of v, (iii) each neighbor u ∈ v↙ is below and to the left of v, (iv) each neighbor u ∈ v↘ is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis.
      PubDate: Mon, 17 Sep 2018 00:00:00 GMT
  • A Mazing 2+ϵ Approximation for Unsplittable Flow on a Path
    • Abstract: Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Andreas Wiese

      We study the problem of unsplittable flow on a path (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small-enough fraction Δ of the capacity along its subpath (Δ-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding.
      PubDate: Mon, 17 Sep 2018 00:00:00 GMT
  • Online Submodular Maximization with Free Disposal
    • Abstract: T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang

      We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access. For k-uniform matroids, we give a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches 1/α∞≈ 0.3178 as k approaches infinity, improving the previous best ratio of 0.25 by Chakrabarti and Kale (IPCO 2014), Buchbinder et al.
      PubDate: Mon, 17 Sep 2018 00:00:00 GMT
  • Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and
           the Lovász Local Lemma
    • Abstract: David G. Harris

      Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of papers, beginning with Luby (1993) and continuing with Berger and Rompel (1991) and Chari et al. (2000), showed that these techniques can be combined to give deterministic parallel algorithms for combinatorial optimization problems involving sums of w-juntas. We improve these algorithms through derandomized variable partitioning, reducing the processor complexity to essentially independent of w and time complexity to linear in w. As a key subroutine, we give a new algorithm to generate a probability space which can fool a given set of neighborhoods.
      PubDate: Tue, 28 Aug 2018 00:00:00 GMT
  • Streaming Algorithms for Estimating the Matching Size in Planar Graphs and
    • Abstract: Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak

      We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that, with high probability, estimates the size of a maximum matching within a constant factor using Õ(n2/3) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space.
      PubDate: Tue, 28 Aug 2018 00:00:00 GMT
  • Conditional Lower Bounds for All-Pairs Max-Flow
    • Abstract: Robert Krauthgamer, Ohad Trabelsi

      We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on n nodes, m edges, and capacities in the range [1‥n], which we call the All-Pairs Max-Flow problem, cannot be solved in time that is significantly faster (i.e., by a polynomial factor) than O(n3) even for sparse graphs, namely m = O(n); thus for general m, it cannot be solved significantly faster than O(n2m). Since a single maximum st-flow can be solved in time Õ(m√n) [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to Ω˜(n3/2) computations of maximum st-flow, which strongly separates the directed case from the undirected one.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • The Dependent Doors Problem: An Investigation into Sequential Decisions
           without Feedback
    • Abstract: Amos Korman, Yoav Rodeh

      We introduce the dependent doors problem as an abstraction for situations in which one must perform a sequence of dependent decisions, without receiving feedback information on the effectiveness of previously made actions. Informally, the problem considers a set of d doors that are initially closed, and the aim is to open all of them as fast as possible. To open a door, the algorithm knocks on it, and it might open or not according to some probability distribution. This distribution may depend on which other doors are currently open, as well as on which other doors were open during each of the previous knocks on that door.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • An Efficient Representation for Filtrations of Simplicial Complexes
    • Abstract: Jean-Daniel Boissonnat, Karthik C. S.

      A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. To represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica’14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • Approximation Guarantees for the Minimum Linear Arrangement Problem by
           Higher Eigenvalues
    • Abstract: Suguru Tamaki, Yuichi Yoshida

      Given an n-vertex undirected graph G = (V,E) and positive edge weights {we}e∈E, a linear arrangement is a permutation π : V → {1, 2, …, n}. The value of the arrangement is val(G, π) := 1/n∑ e ={u, v} ∈ E we|π(u) − π (v)|. In the minimum linear arrangement problem, the goal is to find a linear arrangement π * that achieves val(G, π*) = MLA(G) := min π val(G, π). In this article, we show that for any ε > 0 and positive integer r, there is an nO(r/&epsis;)-time randomized algorithm that, given a graph G, returns a linear arrangement π, such that val(G, π) ≤ (1 + 2/(1 − ϵ)λr(L)) MLA(G) + O(√log n/n ∑ e ∈ E we) with high probability, where L is the normalized Laplacian of G and λr(L) is the rth smallest eigenvalue of L.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • An Efficient Algorithm for Computing High-Quality Paths amid Polygonal
    • Abstract: Pankaj K. Agarwal, Kyle Fox, Oren Salzman

      We study a path-planning problem amid a set O of obstacles in R2, in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ϵ ∈ (0, 1].
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic
    • Abstract: Omer Gold, Micha Sharir

      Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = Rd are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • Packing Groups of Items into Multiple Knapsacks
    • Abstract: Lin Chen, Guochuan Zhang

      We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be.
      PubDate: Tue, 21 Aug 2018 00:00:00 GMT
  • ACM Transactions on Algorithms (TALG) Volume 14 Issue 4, August 2018
    • PubDate: Thu, 09 Aug 2018 00:00:00 GMT
  • Graph Reconstruction and Verification
    • Abstract: Sampath Kannan, Claire Mathieu, Hang Zhou

      How efficiently can we find an unknown graph using distance or shortest path queries between its vertices' We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G. In the verification problem, we are given a hypothetical graph Ĝ and want to check whether G is equal to Ĝ. We provide a randomized algorithm for reconstruction using Õ(n&frac;32) distance queries, based on Voronoi cell decomposition. Next, we analyze natural greedy algorithms for reconstruction using a shortest path oracle and also for verification using either oracle, and show that their query complexity is n1+o(1).
      PubDate: Thu, 09 Aug 2018 00:00:00 GMT
  • Batched Point Location in SINR Diagrams via Algebraic Tools
    • Abstract: Boris Aronov, Matthew J. Katz

      The SINR (Signal to Interference plus Noise Ratio) model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard. Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several articles.
      PubDate: Thu, 09 Aug 2018 00:00:00 GMT
  • Adaptive Computation of the Swap-Insert Correction Distance
    • Abstract: Jérémy Barbay, Pablo Pérez-Lantero

      The Swap-Insert Correction distance from a string S of length n to another string L of length m ≥ n on the alphabet [1‥σ] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size σ of the alphabet. We describe an algorithm computing this distance in time within O(σ 2nmgσ−1), where for each α ∈ [1‥σ] there are nα occurrences of α in S, mα occurrences of α in L, and where g = max α∈[1‥σ] min{nα, mα − nα} is a new parameter of the analysis, measuring one aspect of the difficulty of the instance.
      PubDate: Thu, 09 Aug 2018 00:00:00 GMT
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
Home (Search)
Subjects A-Z
Publishers A-Z
Your IP address:
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-