ABSTRACT Nearest, Farthest, and Cheapest Insertion are three well‐known polynomial‐time approximation algorithms for the Traveling Salesman Problem (TSP). This paper aims to report on a fourth insertion algorithm, called Largest Insertion, from both a theoretical and an experimental viewpoint. On the theoretical side, the worst‐case performance of the algorithm is studied: In particular, it is shown that there exist instances for which the value of the solution computed by Largest Insertion approaches three times the optimum in the Euclidean plane. On the experimental side, the outcome of computational tests is reported: When compared with the other three insertion algorithms, Largest Insertion scores second on random Euclidean instances and first on large random graphical instances.

In this work, we introduce Basilisk, a high-level architectural pattern designed to facilitate interoperability among various languages, platforms, and ecosystems. The pursuit of language-independent software development is highly desirable, enabling developers to utilize existing software products with most programming languages. Achieving platform independence is equally advantageous, allowing code deployment on different platforms effortlessly. While the development community has often aimed for either language or platform independence, Basilisk aims to combine both into a single product. To realize this dual objective, Basilisk employs two fundamental components. The first is a transpilation infrastructure used to render software products language-independent. The second is an abstraction layer over platforms, enabling the creation of platform-independent software products. To illustrate Basilisk’s potential, we introduce Hydra, a one-to-many, declarative transpilation infrastructure. Hydra has been utilized to develop transpilers from HydraKernel (source language) to various target languages, including D, C++, C#, Scala, Ruby, Hy, and Python. Additionally, we instantiate the abstraction layer in Wyvern, a low-level embedded domain-specific language for GPU programming, supporting any Vulkan-compatible GPU. With the Hydra transpilation infrastructure, Wyvern becomes available for D, C++, C#, Scala, Ruby, Hy, and Python. We evaluate Basilisk through the instantiation of Hydra and Wyvern, writing five algorithms from the Rodinia suite for the seven available languages, totaling 35 benchmarks. These benchmarks are executed on four different hardware platforms.

In this paper we give a structural characterization and extend the tractability frontier of the Simple Temporal Problem (STP) by defining the class of the Extended Simple Temporal Problem (ESTP), which augments STP with strict inequalities and monotone Boolean formulae on inequations (i.e., formulae involving the operations of conjunction, disjunction and parenthesization). A polynomial-time algorithm is provided to solve ESTP, faster than previous state-of-the-art algorithms for other extensions of STP that had been considered in the literature, all encompassed by ESTP. We show the practical competitiveness of our approach through a proof-of-concept implementation and an experimental evaluation involving also state-of-the-art SMT solvers.

When playing from pixels, AIs share some of the struggles that humans face when playing a game, namely not knowing its internal state. In this paper we begin the exploration of the AI-playing-from-pixels problem for Touhou, a bullet hell game. Albeit being a massively popular game in some niches, the community has yet to produce an AI capable of beating it, while looking only at pixels, in Lunatic mode, the hardest difficulty. We propose, as a first step, to build a semantic segmentation model to create a bridge to the internal-state-looking AIs. To achieve this, we created a dataset to train models for this task. This dataset is procedurally generated using manually labeled assets from classic era Touhou games. After selecting five state-of-the-art real-time semantic segmentation networks, we trained them using our dataset. The results indicate that the models produced have a high classification performance over the validation set. However all models, but one, are too slow to run in real-time at the game's target frame rate. On real game footage the models show promising results, but the dataset needs to be strengthen to account for noise sources in the real game.

Games have a role in many aspects of science, technology, and society. Also, games attract humans' interest and offer unique learning opportunities. Indeed, the role of games in education has a long tradition. In this paper we introduce Code Colosseum, a platform that takes competitive programming in the direction of games, instead of problems. By taking this direction, we aim to create a more engaging environment for students to compete in. The platform allows programs written by the contestants to compete in a realtime multiplayer game. The platform also allows to spectate the matches between the programs. The design and implementation of Code Colosseum has been kept as simple as possible, to facilitate participation, maintenance and setup. To assess the effectiveness of the approach, we organized a tournament with 16 students, from both high schools and universities, as a pilot experience for Code Colosseum. In this tournament they created programs to play the Royal Game of Ur, a board racing game. The feedback from the students about the experience was positive, and the suggestions received will be implemented for future experiences.

In this paper we discuss the use of Analytics in oii-web, an online programming contest training system. We first provide an overview of the challenges in training for programming contests. Then we discuss the data collected in these years using oii-web, a platform devoted to the training of students for the Italian Olympiads in Informatics (Olimpiadi Italiane di Informatica - OII), and analyze them comparing two distinct groups of users in two distinct platforms built on oii-web, one devoted to students and one to their teachers. Most notably, the two groups are more similar than one would expect when dealing with programming contest training.