Asish Mukhopadhyay, Daniel John, Srivatsan Vasudevan
In this paper, we show that unswitchable graphs are a proper subclass of split graphs, and exploit this fact to propose efficient algorithms for their recognition and generation.
We show how Frieze's analysis of subset sum solving using lattices can be done with out any large constants and without flipping. We apply the variant without the large constant to inputs with noise.
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
The Mersenne-Twister is one of the most popular generators of uniform pseudo-random numbers. It is used in many numerical libraries and software. In this paper, we look at the Komolgorov entropy of the original Mersenne-Twister, as well as of more modern variations such as the 64-bit Mersenne-Twisters, the Well generators, and the Melg generators.
We present an algorithm for bounding the probability of r-core formation in k-uniform hypergraphs. Understanding the probability of core formation is useful in numerous applications including bounds on the failure rate of Invertible Bloom Lookup Tables (IBLTs) and the probability that a boolean formula is satisfiable.
This article identifies a key algorithmic ingredient in the edge-weighted online matching algorithm by Zadimoghaddam (2017) and presents a simplified algorithm and its analysis to demonstrate how it works in the unweighted case.
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n ≥ 6 admits a power dominating set of size at most (n−2)/4 .
Kyle Hasenstab, Aaron Scheffler, Donatello Telesca
et al.
Summary The electroencephalography (EEG) data created in event-related potential (ERP) experiments have a complex high-dimensional structure. Each stimulus presentation, or trial, generates an ERP waveform which is an instance of functional data. The experiments are made up of sequences of multiple trials, resulting in longitudinal functional data and moreover, responses are recorded at multiple electrodes on the scalp, adding an electrode dimension. Traditional EEG analyses involve multiple simplifications of this structure to increase the signal-to-noise ratio, effectively collapsing the functional and longitudinal components by identifying key features of the ERPs and averaging them across trials. Motivated by an implicit learning paradigm used in autism research in which the functional, longitudinal, and electrode components all have critical interpretations, we propose a multidimensional functional principal components analysis (MD-FPCA) technique which does not collapse any of the dimensions of the ERP data. The proposed decomposition is based on separation of the total variation into subject and subunit level variation which are further decomposed in a two-stage functional principal components analysis. The proposed methodology is shown to be useful for modeling longitudinal trends in the ERP functions, leading to novel insights into the learning patterns of children with Autism Spectrum Disorder (ASD) and their typically developing peers as well as comparisons between the two groups. Finite sample properties of MD-FPCA are further studied via extensive simulations.
In this paper I present a 3SAT algorithm based on the randomized algorithm of Papadimitriou from 1991, and Schoning from 1991. We also present strong arguments that this algorithm finds a solution (if it exists) for a 3SAT problem with high probability in polynomial time.
In this paper, ellipsoid method for linear programming is derived using only minimal knowledge of algebra and matrices. Unfortunately, most authors first describe the algorithm, then later prove its correctness, which requires a good knowledge of linear algebra.
In this paper we give an infinite family of strings for which the length of the Lempel-Ziv'77 parse is a factor $Ω(\log n/\log\log n)$ smaller than the smallest run-length grammar.
We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give amortized constant amortized time for insertion.
In this short note, the dual problem for the traveling salesman problem is constructed through the classic Lagrangian. The existence of optimality conditions is expressed as a corresponding inverse problem. A general 4-cities instance is given, and the numerical experiment shows that the classic Lagrangian may not be applicable to the traveling salesman problem.
In this paper, we present an exact algorithm for the Steiner tree problem. The algorithm is based on certain pre-computed index structures. Our algorithm offers a practical solution for the Steiner tree problems on graphs of large size and bounded number of terminals.
Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment, we introduce in this paper the concepts of strong simultaneous approximation ratio (SAR) and weak simultaneous approximation ratio (WAR). Then we study the two parameters under various scheduling environments, such as, non-preemptive, preemptive or fractional scheduling on identical, related or unrelated machines.
This paper describes a new and purely functional implementation technique of binary heaps. A binary heap is a tree-based data structure that implements priority queue operations (insert, remove, minimum/maximum) and guarantees at worst logarithmic running time for them. Approaches and ideas described in this paper present a simple and asymptotically optimal implementation of immutable binary heap.
For all practical purposes, the Micali-Vazirani general graph maximum matching algorithm is still the most efficient known algorithm for the problem. The purpose of this paper is to provide a complete proof of correctness of the algorithm in the simplest possible terms; graph-theoretic machinery developed for this purpose also helps simplify the algorithm.
Alexis Darrasse, Konstantinos Panagiotou, Olivier Roussel
et al.
This paper is devoted to the construction of Boltzmann samplers according to various distributions, and uses stochastic bias on the parameter of a Boltzmann sampler, to produce a sampler with a different distribution for the size of the output. As a significant application, we produce Boltzmann samplers for words defined by regular specifications containing shuffle operators and linear recursions. This sampler has linear complexity in the size of the output, where the complexity is measured in terms of real-arithmetic operations and evaluations of generating functions.
We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colored with a given number of colors.