Data Structures And Algorithms
SFCM-R: A novel algorithm for the hamiltonian sequence problem (1902.06713v2)
Cícero A. de Lima
2019-02-18
A hamiltonian sequence is a path walk
that can be a hamiltonian path or hamiltonian circuit. Determining whether such hamiltonian sequence exists in a given graph is a NP-Complete problem. In this paper, a novel algorithm for hamiltonian sequence problem is proposed. The proposed algorithm assumes that has potential forbidden minors that prevent a potential hamiltonian sequence from being a hamiltonian sequence. The algorithm's goal is to degenerate such potential forbidden minors in a two-phrase process. In first phrase, the algorithm passes through constructing a potential hamiltonian sequence with the aim of degenerating these potential forbidden minors. The algorithm, in turn, tries to reconstruct in second phrase by using a goal-oriented approach.
Coresets for Ordered Weighted Clustering (1903.04351v1)
Vladimir Braverman, Shaofeng H. -C. Jiang, Robert Krauthgamer, Xuan Wu
2019-03-11
We design coresets for Ordered k-Median, a generalization of classical clustering problems such as k-Median and k-Center, that offers a more flexible data analysis, like easily combining multiple objectives (e.g., to increase fairness or for Pareto optimization). Its objective function is defined via the Ordered Weighted Averaging (OWA) paradigm of Yager (1988), where data points are weighted according to a predefined weight vector, but in order of their contribution to the objective (distance from the centers). A powerful data-reduction technique, called a coreset, is to summarize a point set
in into a small (weighted) point set , such that for every set of potential centers, the objective value of the coreset approximates that of within factor . When there are multiple objectives (weights), the above standard coreset might have limited usefulness, whereas in a \emph{simultaneous} coreset, which was introduced recently by Bachem and Lucic and Lattanzi (2018), the above approximation holds for all weights (in addition to all centers). Our main result is a construction of a simultaneous coreset of size for Ordered k-Median. To validate the efficacy of our coreset construction we ran experiments on a real geographical data set. We find that our algorithm produces a small coreset, which translates to a massive speedup of clustering computations, while maintaining high accuracy for a range of weights.
ALLSAT compressed with wildcards: All k-models of a BDD (1703.08511v3)
Marcel Wild
2017-03-24
Given a Binary Decision Diagram of a Boolean function \phi in variables, all N many k-ones models of \phi can be enumerated in time polynomial in n and N. Although this only guarantees enumeraton one-by-one, in practise compression (using wildcards) is often possible.
A Simple Algorithm for Computing the Document Array (1812.09094v2)
Felipe A. Louza
2018-12-21
We present a simple algorithm for computing the document array given the string collection and its suffix array as input. Our algorithm runs in linear time using constant additional space for strings from constant alphabets.
Efficient Synchronization of State-based CRDTs (1803.02750v3)
Vitor Enes, Paulo Sérgio Almeida, Carlos Baquero, João Leitão
2018-03-07
To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronisation algorithms for Delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than State-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) evaluate the improved algorithms.
Bus Manufacturing Workshop Scheduling Method with Routing Buffer (1903.04097v1)
Zhonghua Han, Jingyuan Zhang, Xiaoting Dong, Yuanwei Qi
2019-03-11
Aiming at solving the problem that the moving route is complicated and the scheduling is difficult in the routing buffer of the bus in the manufacturing workshop, a routing buffer mathematical programming model for bus manufacturing workshop is proposed. We design a moving approach for minimizing the total setup cost for moving in routing buffer. The framework and the solution ofthe optimization problem of such a bus manufacturing workshop scheduling with routing buffer arepresented. The evaluation results show that, comparing with the irregularly guided moving method, the proposed method can better guide the bus movement in routing buffer by reducing the total setup time of all buses processed at the next stage, and obtaining a better scheduling optimization solution with minimize maximum total completion time.
Asymptotically faster algorithm for counting self-avoiding walks and self-avoiding polygons (1903.04054v1)
Samuel Zbarsky
2019-03-10
We give an algorithm for counting self-avoiding walks or self-avoiding polygons that runs in time
on 2-dimensional lattices and time on -dimensional lattices for .
Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems (1903.03944v1)
Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, Christopher A. Wilkens
2019-03-10
We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a
fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor approaches when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast approaches , is near optimal: we give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. In the offline setting we give a fast algorithm to solve very large LPs with both packing and covering constraints. We give algorithms to approximately solve (within a factor of ) the mixed packing-covering problem with oracle calls where the constraint matrix of this LP has dimension , the success probability of the algorithm is , and quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing and the adwords problem.
Complexity of computing the anti-Ramsey numbers (1810.08004v2)
Saeed Akhoondian Amiri, Alexandru Popa, Golnoosh Shahkarami, Hossein Vahidi
2018-10-18
The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd"os, Simonovits and S'os. For given graphs
and the anti-Ramsey number is defined to be the maximum number such that there exists an assignment of colors to the edges of in which every copy of in has at least two edges with the same color. Precolored version of the problem is defined in a similar way except that the input graph is given with some fixed colors on some of the edges. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. In this paper we study the complexity of computing the anti-Ramsey number , where is a path of length . Firstly, we show that computing for any odd value of is NP-hard. Then, we show that even approximating to a factor of is already hard in -partite graphs, unless . We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails already for . On the positive side we introduce the notion of color connected coloring, which leads to polynomial time algorithm in trees and we show the approximability of the problem on special classes of graphs.
Superseding traditional indexes by orchestrating learning and geometry (1903.00507v3)
Giorgio Vinciguerra, Paolo Ferragina, Michele Miccinesi
2019-03-01
We design the first learned index that solves the dictionary problem with time and space complexity provably better than classic data structures for hierarchical memories, such as B-trees, and modern learned indexes. We call our solution the Piecewise Geometric Model index (PGM-index) because it turns the indexing of a sequence of keys into the coverage of a sequence of 2D-points via linear models (i.e. segments) suitably learned to trade query time vs space efficiency. This idea comes from some known heuristic results which we strengthen by showing that the minimal number of such segments can be computed via known and optimal streaming algorithms. Our index is then obtained by recursively applying this geometric idea that guarantees a smoothed adaptation to the "geometric complexity" of the input data. Finally, we propose a variant of the index that adapts not only to the distribution of the dictionary keys but also to their access frequencies, thus obtaining the first distribution-aware learned index. The second main contribution of this paper is the proposal and study of the concept of Multicriteria Data Structure, namely one that asks a data structure to adapt in an automatic way to the constraints imposed by the application of use. We show that our index is a multicriteria data structure because its significant flexibility in storage and query time can be exploited by a properly designed optimisation algorithm that efficiently finds its best design setting in order to match the input constraints. A thorough experimental analysis shows that our index and its multicriteria variant improve uniformly, over both time and space, classic and learned indexes up to several orders of magnitude.