Search

In this work we represent the Optimal Stable Marriage problem as a Soft Constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools.

In this paper we describe two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. We then compare the two approaches and we discuss the relationship between them. The two frameworks have been independently introduced in [2] and [28].

Soft constraints are very flexible and expressive. However, they may also be very complex to handle. For this reason, it may be convenient in several cases to pass to an abstract version of a given soft problem, and then bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster.

Tradeoffs have been proposed in the literature as an approach to resolving over-constrainedness in interactive constraint-based tools, such as product configurators. It has been reported how tradeoffs can be modeled as additional constraints. This paper presents a formal framework for tradeoff generation based on the semiring approach to soft constraints. In particular, user preferences and tradeoffs are, respectively, represented as soft constraints and as an entailment operator. The entailment operator is used to interactively generate new constraints representing tradeoffs. The framework we present is well-motivated by real-world approaches that exploit tradeoff generation in online buying and configuration processes.

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold α and degradation δ for substitutability and interchangeability, (αsubstitutability/interchangeability and δsubstitutability/interchangeability respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. We give efficient algorithms to compute (δ/α)interchangeable sets of values for a large class of SCSPs.

The first obstacle that regular users encounter when setting up a node for a public blockchain is the time taken for downloading all the data needed for the node to start operating correctly. In fact, this may last from hours to weeks for the major networks. Our contribution is twofold. Firstly, we show a design that enables mining and validation of new blocks keeping only a very small state. Secondly, we show that it is possible to store the state of the blockchain in a distributed hash table obtaining a wide spectrum of trade-offs between storage committed by the nodes and replication factor. Our proposal is independent from the consensus algorithm adopted, and copes well with transactions that involve smart contracts., 13 pages, 3 figures, conference (DLT19)

In graph theory connectivity is stated, prevailingly, in terms of paths. While exploiting a proof assistant to check formal reasoning about graphs, we chose to work with an alternative characterization of connectivity: for, within the framework of the underlying set theory, it requires virtually no preparatory notions. We say that a graphs devoid of isolated vertices is connected if no subset of its set of edges, other than the empty set and the set of all edges, is vertex disjoint from its complementary set. Before we can work with this notion smoothly, we must prove that every connected graph has a non-cut vertex, i.e., a vertex whose removal does not disrupt connectivity. This paper presents such a proof in accurate formal terms and copes with hypergraphs to achieve greater generality.