Data Structures And Algorithms | 2019-07-11
Data Structures And Algorithms
Better Sample -- Random Subset Sum in 
and its Impact on Decoding Random Linear Codes (1907.04295v1)
Andre Esser, Alexander May
2019-07-09
We propose a new heuristic algorithm for solving random subset sum instances
, which play a crucial role in cryptographic constructions. Our algorithm is search tree-based and solves the instances in a divide-and-conquer method using the representation method. From a high level perspective, our algorithm is similar to the algorithm of Howgrave-Graham-Joux (HGJ) and Becker-Coron-Joux (BCJ), but instead of enumerating the initial lists we sample candidate solutions. So whereas HGJ and BCJ are based on combinatorics, our analysis is stochastic. Our sampling technique introduces variance that increases the amount of representations and gives our algorithm more optimization flexibility. This results in the remarkable and natural property that we improve with increasing search tree depth. Whereas BCJ achieves the currently best known (heuristic) run time
for random subset sum, we improve (heuristically) down to
. We also apply our subset algorithm to the decoding of random binary linear codes, where we improve the best known run time of the Becker-Joux-May-Meurer algorithm from
in the half distance decoding setting down to
.
Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex --- (1907.04279v1)
Takanori Maehara, So Nakashima, Yutaro Yamaguchi
2019-07-09
We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a
approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of a distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions, such that the multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property of the continuous greedy algorithm.
Reconstruction under outliers for Fourier-sparse functions (1907.04274v1)
Xue Chen, Anindya De
2019-07-09
We consider the problem of learning an unknown
with a sparse Fourier spectrum in the presence of outlier noise. In particular, the algorithm has access to a noisy oracle for (an unknown)
-sparse; (ii) at any query point
, the oracle returns
such that with probability
,
. However, with probability
, the error
can be arbitrarily large. We study Fourier sparse functions over both the discrete cube
and the torus
and for both these domains, we design efficient algorithms which can tolerate any
fraction of outliers. We note that the analogous problem for low-degree polynomials has recently been studied in several works~[AK03, GZ16, KKP17] and similar algorithmic guarantees are known in that setting. While our main results pertain to the case where the location of the outliers, i.e.,
is randomly distributed, we also study the case where the outliers are adversarially located. In particular, we show that over the torus, assuming that the Fourier transform satisfies a certain \emph{granularity} condition, there is a sample efficient algorithm to tolerate
fraction of outliers and further, that this is not possible without such a granularity condition. Finally, while not the principal thrust, our techniques also allow us non-trivially improve on learning low-degree functions
Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number (1906.09680v2)
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
2019-06-24
In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no fine-grained analysis has been given for the non-maximal variant. From the main result, we propose an algorithm
for the non-maximal variant that runs in
amortized time and linear space, where
is the clique number, i.e., the maximum size of a clique in an input graph. Note that
-free graphs for any fixed graph
Linear MIM-Width of Trees (1907.04132v1)
Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset
2019-07-09
We provide an
algorithm computing the linear maximum induced matching width of a tree and an optimal layout.
-Gather Clustering and -Gathering on Spider: FPT Algorithms and Hardness (1907.04088v1)
Soh Kumabe, Takanori Maehara
2019-07-09
We consider min-max
PTAS and Exact Algorithms for -Gathering Problems on Tree (1907.04087v1)
Soh Kumabe, Takanori Maehara
2019-07-09
r-gathering problem is a variant of facility location problems. In this problem, we are given a set of users and a set of facilities on same metric space. We open some of the facilities and assign each user to an open facility, so that at least r users are assigned to every open facility. We aim to minimize the maximum distance between user and assigned facility. In general, this problem is NP-hard and admit an approximation algorithm with factor 3. It is known that the problem does not admit any approximation algorithm within a factor less than 3. In our another paper, we proved that this problem is NP-hard even on spider, which is a special case of tree metric. In this paper, we concentrate on the problems on a tree. First, we give a PTAS for r-gathering problem on a tree. Furthermore, we give PTAS for some variants of the problems on a tree, and also give exact polynomial-time algorithms for another variants of r-gathering problem on a tree.
Stochastic Monotone Submodular Maximization with Queries (1907.04083v1)
Takanori Maehara, Yutaro Yamaguchi
2019-07-09
We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain defined on a finite set, and our goal is to find a feasible solution that maximizes the objective function. A special part of the problem is that each element in the finite set has a random hidden state, active or inactive, only the active elements contribute to the objective value, and we can conduct a query to an element to reveal its hidden state. The goal is to obtain a feasible solution having a large objective value by conducting a small number of queries. This is the first attempt to consider nonlinear objective functions in such a stochastic model. We prove that the problem admits a good query strategy if the feasible domain has a uniform exchange property. This result generalizes Blum et al.'s result on the unweighted matching problem and Behnezhad and Reyhani's result on the weighted matching problem in both objective function and feasible domain.
Trustworthy Graph Algorithms (1907.04065v1)
Mohammad Abdulaziz, Kurt Mehlhorn, Tobias Nipkow
2019-07-09
The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching.
Complexity of planar signed graph homomorphisms to cycles (1907.03266v2)
François Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem, Théo Pierron
2019-07-07
We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve the edge-signs. Special homomorphisms of signed graphs, called s-homomorphisms, have been studied. In an s-homomorphism, we allow, before the mapping, to perform any number of switchings on the source signed graph. This concept has been extensively studied, and a full complexity classification (polynomial or NP-complete) for s-homomorphism to a fixed target signed graph has recently been obtained. Such a dichotomy is not known when we restrict the input graph to be planar (not even for non-signed graph homomorphisms). We show that deciding whether a (non-signed) planar graph admits a homomorphism to the square
of a cycle with
, or to the circular clique
with
, are NP-complete problems. We use these results to show that deciding whether a planar signed graph admits an s-homomorphism to an unbalanced even cycle is NP-complete. (A cycle is unbalanced if it has an odd number of negative edges). We deduce a complete complexity dichotomy for the planar s-homomorphism problem with any signed cycle as a target. We also study further restrictions involving the maximum degree and the girth of the input signed graph. We prove that planar s-homomorphism problems to signed cycles remain NP-complete even for inputs of maximum degree~
(except for the case of unbalanced
-cycles, for which we show this for maximum degree~
, the problem for signed bipartite planar inputs of girth