Refine
Has Fulltext
- no (13)
Document Type
- Article (13) (remove)
Language
- English (13)
Is part of the Bibliography
- yes (13)
Keywords
- Theory (2)
- Unique column combination (2)
- APX-hardness (1)
- Ant colony optimization (1)
- Data profiling (1)
- Enumeration algorithm (1)
- Estimation-of-distribution algorithm (1)
- Evolutionary algorithms (1)
- Holant problems (1)
- Matroids (1)
- Minimal hitting set (1)
- Multi-objective optimization (1)
- Mutation operators (1)
- Noisy Fitness (1)
- Parking search (1)
- Random graphs (1)
- Run time analysis (1)
- Runtime analysis (1)
- Submodular function (1)
- Submodular functions (1)
- Subset selection (1)
- Transversal hypergraph (1)
- Unbiasedness (1)
- W[3]-Completeness (1)
- W[3]-completeness (1)
- approximate counting (1)
- approximation (1)
- bidirectional shortest path (1)
- constrained optimization (1)
- data profiling (1)
- dependency (1)
- deterministic properties (1)
- deterministic random walk (1)
- enumeration complexity (1)
- field study (1)
- functional dependency (1)
- graph (1)
- hyperbolic geometry (1)
- inclusion (1)
- parameterized complexity (1)
- parsimonious reduction (1)
- partition functions (1)
- polynomials (1)
- power-law (1)
- probabilistic routing (1)
- random graphs (1)
- rotor-router model (1)
- scale-free networks (1)
- single vertex discrepancy (1)
- transversal hypergraph (1)
A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. <br /> To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.