We study the minimum Monitoring Edge Geodetic Set (MEG-Set) problem introduced in [Foucaud et al., CALDAM'23]: given a graph G, we say that an edge is monitored by a pair u,v of vertices if all shortest paths between u and v traverse e; the goal is to find a subset M of vertices of G such that each edge of G is monitored by at least one pair of vertices in M, and |M| is minimized. In this paper, we prove that all polynomial-time approximation algorithms for the minimum MEG-Set problem must have an approximation ratio of Ω(log n), unless 𝖯 = NP. To the best of our knowledge, this is the first non-constant inapproximability result known for this problem. We also strengthen the known NP-hardness of the problem on 2-apex graphs by showing that the same result holds for 1-apex graphs. This leaves open the question of determining whether the problem remains NP-hard on planar (i.e., 0-apex) graphs. On the positive side, we design an algorithm that computes good approximate solutions for hereditary graph classes that admit efficiently computable balanced separators of truly sublinear size. This immediately yields polynomial-time approximation algorithms achieving an approximation ratio of O(n^{1/4} √{log n}) on planar graphs, graphs with bounded genus, and k-apex graphs with k = O(n^{1/4}). On graphs with bounded treewidth, we obtain an approximation ratio of O(log^{3/2} n). This compares favorably with the best-known approximation algorithm for general graphs, which achieves an approximation ratio of O(√{n log n}) via a simple reduction to the Set Cover problem.

In a project partially supported by research grant PANN20_00690 to Italy's CINI National Lab "Informatica e Scuola", we compared the effectiveness of two alternative instructional methods applied to scaffold the learning of iterations for children at grades 2-3. Eight university groups across the Country collaboratively run the project in two successive rounds throughout the year 2022. Teachers' feedback collected across the two rounds helped fine-tune the deployment of the interventions. The experiment results show that the two alternative interventions have measurable outcome differences in the short term.

Let G=(V,E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for using her edge by pursuing only her personal utility. In such a setting, several classic network optimization problems, like for instance many graph traversal problems, asks for solutions in which an edge of G can be used several times. In game-theoretic terms, these problems are known as one-parameter problems, but with a peculiarity: the workload of each agent is a natural number. In this paper we refine the classic notion of monotonicity of an algorithm so as to exactly capture this property, and we then provide a general technique to efficiently develop truthful mechanisms for this family of problems.

Whereas earlier work on spatiotemporal databases generally focused on geometries changing in discrete steps, the emerging area of moving objects databases supports geometries changing continuously. Two important abstractions are moving point and moving region, modelling objects for which only the time-dependent position, or also the shape and extent are relevant, respectively. Examples of the first kind of moving entity are all kinds of vehicles, aircraft, people or animals; of the latter hurricanes, forest fires, forest growth or oil spills in the sea. The goal is to develop data models and query languages as well as DBMS implementations supporting such entities, enabling new kinds of database applications. In earlier work we have proposed an approach based on abstract data types. Hence, moving point or moving region are viewed as data types with suitable operations. For example, a moving point might be projected into the plane, yielding a curve, or a moving region be mapped to a function describing the development of its size, yielding a real-valued function. A careful design of a system of types and operations (an algebra) has been presented, emphasizing completeness, closure, consistency and genericity. This design was given at an abstract level, defining, for example, geometries in terms of infinite point sets. In the next step, a discrete model was presented, offering finite representations and data structures for all the types of the abstract model. The present paper provides the final step towards implementation by studying and developing systematically algorithms for (a large subset of) the operations. Some of them are relatively straightforward; others are quite complex. Algorithms are meant to be used in a database context; we also address filtering techniques and practical issues such as large object management or numeric robustness in the context of an ongoing prototype implementation.