Lunedì 24 settembre – Approximating the Incremental Knapsack Problem

Lunedì 24 settembre 2018 alle ore 12.00, presso la sala riunioni della sez. di Informatica e Automazione del Dipartimento di Ingegneria dell’Università Roma Tre, il prof. Ulrich Pferschy dell’Università di Graz terrà un seminario dal titolo:

Approximating the Incremental Knapsack Problem


We consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon.

In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods.

Joint work with Federico Della Croce and Rosario Scatamacchia


Per informazioni rivolgersi a G. Nicosia (, tel. 06 57333455)

Friday December 9th – Securing Promiscuous Use of Untrusted USB Thumb Drives in Industrial Control Systems

WHEN: Friday December 9th at 14:30
WHERE: Via della Vasca Navale, 79 – Meeting room (1.10) on 1st floor
TITLE: Securing Promiscuous Use of Untrusted USB Thumb Drives in Industrial Control Systems

ABSTRACT — Industrial Control Systems (ICS) are sensible targets
for high profile attackers and advanced persistent threats, which
are known to exploit USB thumb drives as an effective spreading
vector. In ICSes, these devices are widely used to transfer files
among disconnected systems and represent a serious security
risks, since, they may be promiscuously used in both critical and
regular systems. We show a method that adopts cryptographic
techniques to inhibit critical machines from reading possibly
malicious files coming from regular machines on untrusted USB
thumb drives. Our approach exposes limited attack surface for
any malware, even those based on zero-days. We do not require
users to change the way they use removable storage devices, or
to authenticate. Our approach can be adopted for disconnected
machines and does not need complex key management. We
describe the architecture of our solution and provide a thorough
analysis of the security of our approach in the ICS context.

TITLE: USBCheckIn: Preventing BadUSB Attacks by Forcing Human-Device Interaction

ABSTRACT — The BadUSB attack leverages the modification of
firmware of USB devices in order to mimic the behaviour of a
keyboard or a mouse and send malicious commands to the host.
This is a new and dreadful threat for any organization. Current
countermeasures either require special USB devices or ask the
user to decide if the device can be used.
We propose a new approach that, before allowing the device
to be used, forces the user to interact with it physically, to
ensure that a real human-interface device is attached. Our
implementation is hardware-based and, hence, can be used with
any host, comprising embedded devices, and also during boot,
i.e., before any operating system is running. Our approach does
not require any special feature from USB devices.

An Efficient Partial Coverage Algorithm for Wireless Sensor Networks


Friday, June 17 at 12:00.

====== Where ======
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor


An Efficient Partial Coverage Algorithm for Wireless Sensor Networks


Habib Mostafaei

PhD student in Computer Science and Automation

Roma Tre University


Wireless sensor networks (WSNs) are currently adopted in a vast variety of domains. Due to practical energy constraints, in this field minimizing sensor energy consumption is a critical challenge. Sleep scheduling approaches give the
opportunity of turning off a subset of the nodes of a network without suspending the monitoring activities performed by the WSN—in order to save energy and increase the lifetime of the sensing system. Our study focuses on partial coverage, targeting scenarios in which the continuous monitoring of a limited portion of the area of interest is enough. In this paper, we present PCLA, an efficient algorithm based on Learning Automata that aims at minimizing the number of sensors to activate, such that a given portion of the area of interest is covered and connectivity among sensors is preserved. Simulation results show how PCLA can select sensors in an efficient way to satisfy the imposed
constraints, thus guaranteeing better performance in terms of both working-node ratio and WSN lifetime. Also, we show how PCLA outperforms state-of-the-art partial-coverage algorithms.

Joint work with A. Montieri, V. Persico, A. Pescape

Seminars – Valentino Di Donato, Marco Di Bartolomeo and Gabriele Lospoto – June 1st @ 2:00PM

=== When ===
  Wednesday, June 1st at 2:00 PM

=== Where ===
  Department of Engineering
  Section of Computer Science and Automation
  Via della Vasca Navale, 79
  Meeting room (1.10) on 1st floor



=== Title ===
  NetFork: Mapping Time to Space in Network Visualization

=== Speaker ===
  Valentino Di Donato
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
Dynamic network visualization aims at representing the evolution of relational information in a readable, scalable, and effective way. A natural approach, called ‘time-to-time mapping’, consists of computing a representation of the network at each time step and animating the transition between subsequent time steps. However, recent literature recommends to represent time-related events by means of static graphic counterparts, realizing the so called ‘time-to-space mapping’. This paradigm has been successfully applied to networks where nodes and edges are subject to a restricted set of events: appearances, disappearances, and attribute changes. In this paper we describe NETFORK, a system that conveys the timings and the impact of path changes that occur in a routing network by suitable time-to-space metaphors, without relying on the time-to-time mapping adopted by the play-back interfaces of alternative network monitoring tools. A user study and a comparison with the state of the art show that users can leverage on high level static representations to quickly assess the quantity and quality of the path dynamics that took place in the network.

Joint work with M. Patrignani and C. Squarcella



=== Title ===
  There is More to Streamgraphs than Movies: Better Aesthetics via Ordering and Lassoing

=== Speaker ===
  Marco Di Bartolomeo
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
Streamgraphs were popularized in 2008 when The New York Times used them to visualize box office revenues for 7500 movies over 21 years. The aesthetics of a streamgraph is affected by three components: the ordering of the layers, the shape of the
lowest curve of the drawing, known as the baseline, and the labels for the layers. As of today, the ordering and baseline computation algorithms proposed in the paper of Byron and Wattenberg are still considered the state of the art. However, their
ordering algorithm exploits statistical properties of the movie revenue data that may not hold in other data. In addition, the baseline optimization is based on a definition of visual energy that in some cases results in considerable amount of visual
distortion. We offer an ordering algorithm that works well regardless of the properties of the input data, and propose a 1-norm based definition of visual energy and the associated solution method that overcomes the limitation of the original baseline
optimization procedure. Furthermore, we propose an efficient layer labeling algorithm that scales linearly to the data size in place of the brute-force algorithm adopted by Byron and Wattenberg. We demonstrate the advantage of our algorithms over
existing techniques on a number of real world data sets.

Joint work with Yifan Hu


=== Title ===
  How to Handle ARP in a Software-Defined Network

=== Speaker ===
  Gabriele Lospoto
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
The Address Resolution Protocol (ARP) enables communication between IP-speaking nodes in a local network by reconstructing the hardware (MAC) address associated with the IP address of an interface. This is not needed in a Software-Defined Network (SDN), because each device can forward packets without the need to learn this association. We tackle the interoperability problem arising between standard network devices (end systems, routers), that rely on ARP, and SDN datapaths, that do not handle ARP packets natively. In particular, we propose a general approach to handle ARP in a SDN, that is applicable in several network scenarios, is transparent for existing devices, and can coexist with any packet forwarding logic implemented in the controller. Our approach reduces ARP traffic by confining it to the edge of SDNs and requires a minimal set of flow entries in the datapaths. We argument about its applicability and confirm it with experiments performed on SDN datapaths from a range of different vendors.

Joint work with Roberto di Lallo, Massimo Rimondini and Giuseppe Di Battista

Wednesday, April 27, 2016 – On information propagation, social influence, and communities

At “Sala riunioni”, first floor, Dipartimento di Ingegneria, Via della Vasca Navale 79, 00149 Roma, Italy
On Wednesday, April 27, 2016
From 12 noon to 1pm
The seminar will feature a presentation by Francesco Bonchi on his recent research in this area. 
Abstract: With the success of online social networks and microblogging platforms such as Facebook, Tumblr, and Twitter, the phenomenon of influence-driven propagations, has recently attracted the interest of computer scientists, sociologists, information technologists, and marketing specialists. In this talk we will take a data mining perspective, discussing what (and how) can be learned from a social network and a database of traces of past propagations over the social network. Starting from one of the key problems in this area, i.e. the identification of influential users, we will provide a brief overview of our recent contributions in this area. We will expose the connection between the phenomenon of information propagation and the existence of communities in social network, and we will go deeper in this new research topic arising at the overlap of information propagation analysis and community detection.

Tuesday, April 5th at 11:30 – Prof. Ulrich Pferschy – On the Quadratic Traveling Salesman Problem


Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor


On the Quadratic Traveling Salesman Problem

The well-known Traveling Salesman Problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. More recently, the following generalization of TSP was introduced: In the Quadratic Traveling Salesman Problem (QTSP) there is a weight associated with every three vertices traversed in succession. As a special case, we also consider the case where these weights correspond to the turning angles of the tour and speak of the angular-metric traveling salesman problem (Angle TSP).
In this talk we apply a rather basic algorithmic idea and perform the separation of the classical subtour elimination constraints on integral solutions only. Surprisingly, it turns out that this approach is faster than the standard fractional separation procedure known from the literature. We also test the combination with strengthened subtour elimination constraints for both variants, but these turn out to slow down the computation. Furthermore, we provide a new ILP linearization for the Angle TSP that needs only a linear number of additional variables while the standard linearization requires a cubic number.
We also consider the maximization version of the QTSP. For the special case of the MaxAngle TSP we can observe an interesting geometric property if the number of vertices is odd. We show that the sum of inner turning angles in an optimal solution always equals pi. This implies that the problem can be solved by the standard ILP model without producing any integral subtours. Moreover, we give a simple constructive polynomial time algorithm to find such an optimal solution. If the number of vertices is even no such property holds.


Small group modeling in cultural heritage – modeling automatic detection of social behavior of museum visitor pairs – Prof. Tsvi Kuflik – Thursday, december 17

Thursday, december 17  at  16:00 – 18:00.

N13 room,  ground floor, Department of Engineering

Via della Vasca Navale, 79, Roma



In many cases, visitors come to a museum in small groups. In these cases, the visitors’ social context has an impact on their museum visit experience. Knowing the social context may allow a system to provide socially-aware services to the visitors. Evidence of the social context can be gained from observing/monitoring the visitors’ social behavior. However, automatic identification of a social context requires on the one hand identifying typical social-behavior patterns, and on the other using relevant sensors that measure various signals and reason about them to detect the visitors’ social behavior. The talk will present such typical social-behavior patterns of visitor pairs, identified by observations, and then, the instrumentation, detection process, reasoning, and analysis of measured signals that enables to detect the visitors’ social behavior. Simple sensors’ data, such as proximity to other visitors, proximity to museum points-of-interest, and visitor orientation were used to detect social synchronization, attention to the social companion, and interest in museum exhibits. The presented approach may allow future research to offer adaptive services to museum visitors based on their social context, to support their group visit experience better.

Graph-Based User Modeling: Make the most out of (freely available) personal data – Prof. Tsvi Kuflik – Wednesday, december 16

Wednesday, December 16 at 16:00-18:00

N13 room,  ground floor, Department of Engineering

Via della Vasca Navale, 79, Roma


Over the years, the area of user modeling (and later on recommendation systems) produced a variety of user modeling techniques. These techniques were developed for modeling and representing the users in order to better understand their needs and provide them with personalized services. The common techniques in use are collaborative filtering and content/feature based, while in specific domains we can find also case-based, demographic and overlay approaches. However, the knowledge represented by these techniques is quite limited. In recent years, with the advent of web 2.0 and the social and semantic web, personal information becomes widely available online in various forms. This poses opportunities as well as major challenges for the classical user modeling approaches – how to make use of this information to enhance user modeling? As a potential solution to the problem, we are exploring the idea of graph-based user modeling representation, as an integrative framework that enables standard and simple representation of users’ characteristics, not limited to a specific technique. In various studies we demonstrated the potential benefits of this approach and it’s possible contribution to user modeling and recommender systems. The talk will briefly present the general idea of graph-based user modeling as well as research results that demonstrate its contribution to a variety of domains and scenarios.