1,721,052 research outputs found
On-line algorithms for satisfiability problems with uncertainty
No full textAbstractIn this paper the problem of the on-line satisfiability of a Horn formula with uncertainty is addressed; we show how to represent a significant class of formulae by weighted directed hypergraphs and we present two algorithms that solve the on-line Horn-SAT problem and find a minimum model for the formula working on the dynamic weighted hypergraph representation. These algorithms make increasing assumptions on the formula and we find that the second one solves the on-line Horn-SAT problem with a total time linear in the size of the formula, matching the optimal result for Boolean Horn formulae
The online Prize-Collecting Traveling Salesman Problem
No full textWe study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O (1)-competitive algorithm that runs in polynomial time. © 2008 Elsevier B.V. All rights reserved
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms
No full textLecture Notes in Computer Science, Springer Verla
Chordality properties on graphs and minimal conceptual connections in semantic data models
No full textAbstractIn this paper the problem of finding a minimal connection among a set of objects that represent conceptual entities in a semantic data model is investigated. If we represent the conceptual structure of reality by means of a graph this problem corresponds to finding a Steiner tree over a given set of nodes. In this paper the case of bipartite graphs is considered and it is shown that, if the bipartite graphs satisfy suitable chordality properties, the Steiner problem may be solved in polynomial time. Furthermore, it is shown that such chordality properties correspond to the concepts of acyclicity that are usually considered in the relational model of data
- …
