Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 16 of 16 for “"hitting set"”.

  1. Geometric Hitting Sets and Their Variants

    … we present efficient</p><p>algorithms for the hitting-set problem and the budgeted hitting-set problem.</p><p>Given a set of objects and a collection of subsets of the objects,</p><p>called ranges, the hitting-set problem asks for a minimum number of </p><p>objects that intersect all the …

    duke Repository record for Geometric Hitting Sets and Their Variants (opens in a new tab)

  2. Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms

    … of randomized approximation algorithms for the hitting set and b-matching problems in hypergraphs. We present a randomized algorithm for the hitting set problem based on linear programming. The analysis of the randomized algorithm rests upon the probabilistic method, more precisely on some …

    cau-kiel Repository record for Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms (opens in a new tab)

  3. New approaches to integer programming

    … approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for …

    gatech Repository record for New approaches to integer programming (opens in a new tab)

  4. A Combinatorial Approach to Protein Mixture - Identification based on Mass Spectrometry Data

    … in its most general from is reformulated as a hitting set problem over (finding transversals of) a hypergraph. The limitations and extent of applicability of this approach, considering different error sources in MS data are addressed.

    chalmers Repository record for A Combinatorial Approach to Protein Mixture - Identification based on Mass Spectrometry Data (opens in a new tab)

  5. Understanding Inconsistency -- A Contribution to the Field of Non-monotonic Reasoning

    … proves a duality between maximal consistent subsets of a propositional knowledge base and minimal hitting sets of each minimal conflict -- the famous hitting set duality. We extend Reiter's result to arbitrary non-monotonic logics. To this end, we develop a refined notion of inconsistency, …

    qucosa-diss

  6. Counter-Example Based Planning Under Uncertainty

    … to reason over succinct representations of sets of initial states. Our algorithm searches over counter-tags, computing their probabilities efficiently by using a d-DNNF representation of discrete probability distributions. We call our algorithm p-CPCES. To address the challenge of …

    anu Repository record for Counter-Example Based Planning Under Uncertainty (opens in a new tab)

  7. Approximation algorithms for independent set problems on hypergraphs

    … algorithms for the Maximum Independent Set and the Minimum Hitting Set problems on hypergraphs. As a hypergraph is a generalization of a graph, the question is whether the best known approximations on graphs can be extended to hypergraphs. We consider greedy, local search and …

    reykjavik Repository record for Approximation algorithms for independent set problems on hypergraphs (opens in a new tab)

  8. Russian doll search algorithms for discrete optimization problems

    … The Steiner triple covering problem is a hitting set problem that corresponds to a search for a vertex cover from a hypergraph. A search for a transitive subtournament from a digraph can be translated to a search for an independent set from a hypergraph. Moreover, the best barbeque problem …

    aalto Repository record for Russian doll search algorithms for discrete optimization problems (opens in a new tab)

  9. A Spectral Decomposition Heuristic for Near Optimal Capture Sets In Consensus Models

    … G=(V,E), consider the problem of selecting a subset of nodes, A, of a fixed size, k, such that the sum expected walk length from V to A, or hitting time, is minimized. This study is motivated by modeling communication models as a random walk on a weighted loopless directed graph where the desired …

    rice Repository record for A Spectral Decomposition Heuristic for Near Optimal Capture Sets In Consensus Models (opens in a new tab)

  10. Derandomizing space-bounded computation via pseudorandom generators and their generalizations

    … derandomization. One such generalization is a hitting set generator (HSG), a standard "one-sided" version of a PRG. Another such generalization, introduced recently by Braverman, Cohen, and Garg [BCG20], is a weighted pseudorandom generator (WPRG), which is similar to a PRG except probability …

    texas Repository record for Derandomizing space-bounded computation via pseudorandom generators and their generalizations (opens in a new tab)

  11. On the parameterized complexity of finding short winning strategies in combinatorial games

    … PSPACE or EXP. In the parameterized complexity setting, Downey and Fellows initiated a study of "short" (or k-move) winning strategy problems. This can be seen as a generalization of "mate-in-k" chess problems, in which the goal is to find a strategy which checkmates your opponent within k moves …

    uvic Repository record for On the parameterized complexity of finding short winning strategies in combinatorial games (opens in a new tab)

  12. Scalable Methods for Phylogenetic Network Inference

    … underlying phylogenetic tree with an additional set of “horizontal” edges. Furthermore, I demonstrate why likelihood computations of networks take orders of magnitude more time when compared to trees. Second, I develop an approach for inference of phylogenetic networks based on pseudo-likelihood …

    rice Repository record for Scalable Methods for Phylogenetic Network Inference (opens in a new tab)

  13. Parameterized algorithms and computational lower bounds: a structural approach

    … problems including Vertex Cover, Independent Set and Dominating Set. We present a set of new techniques that allows us to prove almost tight computational lower bounds for some NP-hard problems, such as Clique, Dominating Set, Hitting Set, Set Cover, and Independent Set. The techniques are …

    tamu Repository record for Parameterized algorithms and computational lower bounds: a structural approach (opens in a new tab)

  14. Monitoring on Graphs: An Exploration into k-Cores, Zero Forcing, and Power Domination

    … transversals. Further, a heuristic for the hitting set of the minimal l-cores is given with its associated valid inequality. Additionally, improved valid inequalities are generated using bounds generated via the girth of the graph. Multiple low order heuristics are explored for finding …

    rice Repository record for Monitoring on Graphs: An Exploration into k-Cores, Zero Forcing, and Power Domination (opens in a new tab)

  15. Covering Problems via Structural Approaches

    The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the …

    waterloo Repository record for Covering Problems via Structural Approaches (opens in a new tab)

  16. Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος

    … a graph in the sense that they both consist of a set of vertices and a set of edges, but they differ in that in a graph the edges have a multiplicity of two (here we consider an edge as a set with two elements, the set of its endpoints), while in a hypergraph the edges have an arbitrary …

    greece Repository record for Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος (opens in a new tab)