Rafael Araujo, Eurinardo Costa, Sulamita Klein, Rudini Sampaio, Ueverton S. Souza
2018-10-18
Given a graph
, let and be the sizes of a minimum and a maximum minimal vertex covers of , respectively. We say that is well covered if (that is, all minimal vertex covers have the same size). Determining if a graph is well covered is a coNP-complete problem. In this paper, we obtain -time and -time algorithms to decide well coveredness, improving results of Boria et. al. (2015). Moreover, using crown decomposition, we show that such problems admit kernels having linear number of vertices. In 2018, Alves et. al. (2018) proved that recognizing well covered graphs is coW[2]-hard when the independence number is the parameter. Contrasting with such coW[2]-hardness, we present an FPT algorithm to decide well coveredness when and the degeneracy of the input graph are aggregate parameters. Finally, we use the primeval decomposition technique to obtain a linear time algorithm for extended -laden graphs and -graphs, which is FPT parameterized by , improving results of Klein et al (2013).
Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, Maximilian Schleich
2018-12-22
Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle's geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k-means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.
Dmitry Kosolobov, Nikita Sivukhin
2018-11-03
Given
strings over the alphabet , the classical Aho--Corasick data structure allows us to find all occurrences of the strings in any text in time using bits of space, where is the number of edges in the trie containing the strings. Fix any constant . We describe a compressed solution for the problem that, provided for a constant , works in time, which is since is constant, and occupies bits of space, for all simultaneously, where is an arbitrary constant and is the th-order empirical entropy of the trie. Hence, we reduce the term in the space bounds of previously best succinct solutions to , thus solving an open problem posed by Belazzougui. Further, we notice that is a worst-case space lower bound for any solution of the problem and, for and constant , our approach allows to achieve bits of space, which gives an evidence that, for , the space of our data structure is theoretically optimal up to the additive term and it is hardly possible to eliminate the term . In addition, we refine the space analysis of previous works by proposing a more appropriate definition for . We also simplify the construction for practice adapting the fixed block compression boosting technique, then implement our data structure, and conduct a number of experiments showing that it is comparable to the state of the art in terms of time and is superior in space.
Ramin Yarinezhad, Seyed Naser Hashemi
2016-10-07
In this paper, we present two approximation algorithms for the directed multi-multiway cut and directed multicut problems. The so called region growing paradigm \cite{1} is modified and used for these two cut problems on directed graphs. By using this paradigm, we give for each problem an approximation algorithm such that both algorithms have the approximate factor
the same as the previous works done on these problems. However, the previous works need to solve linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.
Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, Nathan Srebro
2018-10-28
We study the interplay between sequential decision making and avoiding discrimination against protected groups, when examples arrive online and do not follow distributional assumptions. We consider the most basic extension of classical online learning: "Given a class of predictors that are individually non-discriminatory with respect to a particular metric, how can we combine them to perform as well as the best predictor, while preserving non-discrimination?" Surprisingly we show that this task is unachievable for the prevalent notion of "equalized odds" that requires equal false negative rates and equal false positive rates across groups. On the positive side, for another notion of non-discrimination, "equalized error rates", we show that running separate instances of the classical multiplicative weights algorithm for each group achieves this guarantee. Interestingly, even for this notion, we show that algorithms with stronger performance guarantees than multiplicative weights cannot preserve non-discrimination.
Brahim Chaourar
2019-03-29
Given a graph
, a connected cut is the set of edges of E linking all vertices of U to all vertices of such that the induced subgraphs and are connected. Given a positive weight function defined on , the connected maximum cut problem (CMAX CUT) is to find a connected cut such that is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs. In this paper, we prove that CMAX CUT is polynomial for graphs without as a minor. We deduce a quadratic time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.
Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang
2018-11-12
Neural networks have great success in many machine learning applications, but the fundamental learning theory behind them remains largely unsolved. Learning neural networks is NP-hard, but in practice, simple algorithms like stochastic gradient descent (SGD) often produce good solutions. Moreover, it is observed that overparameterization (that is, designing networks whose number of parameters is larger than statistically needed to perfectly fit the training data) improves both optimization and generalization, appearing to contradict traditional learning theory. In this work, we prove that using overparameterized neural networks with rectified linear units, one can (improperly) learn some notable hypothesis classes, including two and three-layer neural networks with fewer parameters and smooth activations. Moreover, the learning process can be simply done by SGD or its variants in polynomial time using polynomially many samples. We also show that for a fixed sample size, the population risk of the solution found by some SGD variant can be made almost independent of the number of parameters in the overparameterized network.
Igor Nesiolovskiy, Artem Nesiolovskiy
2019-03-29
We offer multiplication method for factoring big natural numbers which extends the group of the Fermat's and Lehman's factorization algorithms and has run-time complexity
. This paper is argued the finiteness of proposed algorithm depending on the value of the factorizable number n. We provide here comparative tests results of related algorithms on a large amount of computational checks. We describe identified advantages of the proposed algorithm over others. The possibilities of algorithm optimization for reducing the complexity of factorization are also shown here.
Efstratios Rappos, Stephan Robert, Philippe Cudré-Mauroux
2019-03-29
We present a novel algorithm to match GPS trajectories onto maps offline (in batch mode) using techniques borrowed from the field of force-directed graph drawing. We consider a simulated physical system where each GPS trajectory is attracted or repelled by the underlying road network via electrical-like forces. We let the system evolve under the action of these physical forces such that individual trajectories are attracted towards candidate roads to obtain a map matching path. Our approach has several advantages compared to traditional, routing-based, algorithms for map matching, including the ability to account for noise and to avoid large detours due to outliers in the data whilst taking into account the underlying topological restrictions (such as one-way roads). Our empirical evaluation using real GPS traces shows that our method produces better map matching results compared to alternative offline map matching algorithms on average, especially for routes in dense, urban areas.
Rayan Chikhi, Jan Holub, Paul Medvedev
2019-03-29
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying k-mer sets has emerged as a shared underlying component. Sets of k-mers have unique features and applications that, over the last ten years, have resulted in many specialized approaches for their representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query k-mer sets. We hope this survey will not only serve as a resource for researchers in the field but also make the area more accessible to outsiders
