for Journals by Title or ISSN
for Articles by Keywords
  Subjects -> MATHEMATICS (Total: 1003 journals)
    - APPLIED MATHEMATICS (82 journals)
    - GEOMETRY AND TOPOLOGY (21 journals)
    - MATHEMATICS (742 journals)
    - MATHEMATICS (GENERAL) (41 journals)
    - NUMERICAL ANALYSIS (22 journals)

MATHEMATICS (742 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: 33)
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: 11)
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: 9)
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: 13)
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: 10)
Anadol University Journal of Science and Technology B : Theoritical Sciences     Open Access  
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: 12)
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  
Annals of West University of Timisoara - Mathematics and Computer Science     Open Access  
Annuaire du Collège de France     Open Access   (Followers: 6)
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: 3)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 14)
Applied Mathematics     Open Access   (Followers: 3)
Applied Mathematics     Open Access   (Followers: 7)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 8)
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: 6)
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-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  
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: 2)
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 Advanced Mathematical Sciences     Open Access  
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: 9)
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: 8)
Czechoslovak Mathematical Journal     Hybrid Journal   (Followers: 1)
Demographic Research     Open Access   (Followers: 13)
Demonstratio Mathematica     Open Access  
Dependence Modeling     Open Access  
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 31)
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: 4)
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   (Followers: 2)
Edited Series on Advances in Nonlinear Science and Complexity     Full-text available via subscription  
Educação Matemática Debate     Open Access  
EduMatSains     Open Access  
Electronic Journal of Combinatorics     Open Access  

        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]
  • Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems
    • Abstract: Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi

      We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For these four problems, kernels with O(k2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this article, we give the first kernels for FVST, CVD, TPT, and Induced P3-Packing with a subquadratic number of vertices.
      PubDate: Tue, 08 Jan 2019 00:00:00 GMT
  • On Problems Equivalent to (min,+)-Convolution
    • Abstract: Marek Cygan, Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk

      In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. This progress has come in the form of conditional lower bounds—reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others. In the (min ,+)-convolution problem, the goal is to compute a sequence (c[i])n−1i=0, where c[k] = mini=0,&ldots; ,k { a[i] + b[k−i]}, given sequences (a[i])n−1i=0 and (b[i])n−1i=0. This can easily be done in O(n2) time, but no O(n2−ϵ) algorithm is known for ϵ> 0.
      PubDate: Tue, 08 Jan 2019 00:00:00 GMT
  • A Dual Descent Algorithm for Node-capacitated Multiflow Problems and Its
    • Abstract: Hiroshi Hirai

      In this article, we develop an O((m log k)MSF(n,m,1))-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with n nodes, m edges, and k terminals, where MSF(n′,m′,γ) denotes the time complexity of solving the maximum submodular flow problem in a network with n′ nodes, m′ edges, and the complexity γ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in O(m n3 log k) time. This is the first combinatorial strongly polynomial time algorithm for this problem.
      PubDate: Thu, 20 Dec 2018 00:00:00 GMT
  • Completeness for First-order Properties on Sparse Structures with
           Algorithmic Applications
    • Abstract: Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams

      Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time O(mk) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O(mk−ε) time for any ε> 0. (Here,>m represents the size of the input structure, i.e., the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to mk/2Θ (√ log n), i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH.
      PubDate: Tue, 18 Dec 2018 00:00:00 GMT
  • Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
    • Abstract: Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

      Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U⊆ V(G) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O (k161 log58k) and asked whether one can design a kernel of size O (k10) [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size O (k12 log10k), inspired by the O (k2) -size kernel for Feedback Vertex Set [Thomassé, TALG 2010].
      PubDate: Sat, 08 Dec 2018 00:00:00 GMT
  • A (2+ε)-Approximation for Maximum Weight Matching in the
           Semi-streaming Model
    • Abstract: Ami Paz, Gregory Schwartzman

      We present a simple deterministic single-pass (2+ε)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves on the currently best known approximation ratio of (4+ε). Our algorithm uses O(nlog2 n) bits of space for constant values of ε. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.
      PubDate: Fri, 07 Dec 2018 00:00:00 GMT
  • Beating Approximation Factor Two for Weighted Tree Augmentation with
           Bounded Costs
    • Abstract: David Adjiashvili

      The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree G=(V,E), an additional set of edges L ⊑ V× V disjoint from E called links and a cost vector c∈ R≥ 0L, WTAP asks to find a minimum-cost set F⊑ L with the property that (V,E∪ F) is 2-edge connected. The special case where cℓ = 1 for all ℓ ∈ L is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present the first improved approximation algorithm for WTAP in more than three decades.
      PubDate: Fri, 07 Dec 2018 00:00:00 GMT
  • Firefighting on Trees Beyond Integrality Gaps
    • Abstract: David Adjiashvili, Andrea Baggio, Rico Zenklusen

      The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this article. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire.
      PubDate: Fri, 07 Dec 2018 00:00:00 GMT
  • Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances
           in Planar Graphs
    • Abstract: Sergio Cabello

      In this article, we show how to compute for n-vertex planar graphs in O(n11/6 polylog(n)) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O(n15/8 polylog(n)) expected time, we can also compute the number of pairs of vertices at distances smaller than a given threshold. These are the first algorithms for these problems using time O(nc) for some constant c< 2, even when restricted to undirected, unweighted planar graphs.
      PubDate: Fri, 07 Dec 2018 00:00:00 GMT
  • Even Delta-Matroids and the Complexity of Planar Boolean CSPs
    • Abstract: Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

      The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat: We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices.
      PubDate: Fri, 07 Dec 2018 00:00:00 GMT
  • Common Tangents of Two Disjoint Polygons in Linear Time and Constant
    • Abstract: Mikkel Abrahamsen, Bartosz Walczak

      We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons—whether they are nested, overlapping, or disjoint—and our algorithm thus also decides this relationship.
      PubDate: Thu, 06 Dec 2018 00:00:00 GMT
  • Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
    • Abstract: Michael Elkin, Ofer Neiman

      Miller et al. [48] devised a distributed1 algorithm in the CONGEST model that, given a parameter k = 1,2,&ldots;, constructs an O(k)-spanner of an input unweighted n-vertex graph with O(n1+1/k) expected edges in O(k) rounds of communication. In this article, we improve the result of Reference [48] by showing a k-round distributed algorithm in the same model that constructs a (2k−1)-spanner with O(n1+1/k}/ε) edges, with probability 1−ε for any ε>0. Moreover, when k=ω(log n), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1+ o(1)), with probability 1−o(1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that are sparse.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • The Simplex Algorithm Is NP-Mighty
    • Abstract: Yann Disser, Martin Skutella

      We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm are NP-mighty. That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This result casts a more favorable light on these algorithms’ exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm’s execution and determining the number of iterations needed are both NP-hard problems.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • An O(log k)-Competitive Algorithm for Generalized Caching
    • Abstract: Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke

      In the generalized caching problem, we have a set of pages and a cache of size k. Each page p has a size wp≥ 1 and fetching cost cp for loading the page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot exceed k. The input consists of a sequence of page requests. If a page is not present in the cache at the time it is requested, it has to be loaded into the cache, incurring a cost of cp. We give a randomized O(log k)-competitive online algorithm for the generalized caching problem, improving the previous bound of O(log2 k) by Bansal, Buchbinder, and Naor (STOC’08).
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • Deterministic Graph Exploration with Advice
    • Abstract: Barun Gorain, Andrzej Pelc

      We consider the fundamental task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,…, d−1. A mobile agent, initially situated at some starting node v, has to visit all nodes and stop. The time of the exploration is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, to explore the graph in a given time, using a deterministic algorithm. Following the paradigm of algorithms with advice, this a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring
    • Abstract: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

      MAX-CUT, EDGE DOMINATING SET, GRAPH COLORING, and HAMILTONIAN CYCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g(k)nf(k) on graphs of clique-width k. Fomin et al. (2010) showed that the running times cannot be improved to g(k)nO(1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f(k) in the running times.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • Improved Analysis of Deterministic Load-Balancing Schemes
    • Abstract: Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemysław uzna&nstrok;ski

      We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • ACM Transactions on Algorithms (TALG) Volume 15 Issue 2, November 2018
    • PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
    • Abstract: Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

      Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness.
      PubDate: Fri, 16 Nov 2018 00:00:00 GMT
  • The Complexity of Independent Set Reconfiguration on Bipartite Graphs
    • Abstract: Daniel Lokshtanov, Amer E. Mouawad

      We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model, the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete.
      PubDate: Tue, 30 Oct 2018 00:00:00 GMT
  • An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion
           Streams and Related Problems
    • Abstract: Arnab Bhattacharyya, Palash Dey, David P. Woodruff

      We give the first optimal bounds for returning the ℓ1-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in { 1, 2, &ldots; , n} and parameters 0 < ϵ < ϕ ⩽ 1, let fi denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which fi ⩾ ϕ m, returns no items j for which fj ⩽ (ϕ −ϵ)m, and returns approximations &ftilde;i with |&ftilde;i − fi| ⩽ ϵ m for each item i that it returns.
      PubDate: Mon, 22 Oct 2018 00:00:00 GMT
  • 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
  • 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
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-