Source author record

Michele Flammini

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory Artificial Intelligence Computational Complexity econ.TH Machine Learning

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Almost Envy-Free Allocations with Connected Bundles

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

preprint2021arXiv

Unavailable Transit Feed Specification: Making it Available with Recurrent Neural Networks

Studies on public transportation in Europe suggest that European inhabitants use buses in ca. 56% of all public transport travels. One of the critical factors affecting such a percentage and more, in general, the demand for public transport services, with an increasing reluctance to use them, is their quality. End-users can perceive quality from various perspectives, including the availability of information, i.e., the access to details about the transit and the provided services. The approach proposed in this paper, using innovative methodologies resorting on data mining and machine learning techniques, aims to make available the unavailable data about public transport. In particular, by mining GPS traces, we manage to reconstruct the complete transit graph of public transport. The approach has been successfully validated on a real dataset collected from the local bus system of the city of L'Aquila (Italy). The experimental results demonstrate that the proposed approach and implemented framework are both effective and efficient, thus being ready for deployment.

preprint2013arXiv

Approximating the Revenue Maximization Problem with Sharp Demands

We consider the revenue maximization problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly $d_i$ items, and each item $j$ gives a benefit $v_{ij}$ to buyer $i$ . We distinguish between unrelated and related valuations. In the former case, the benefit $v_{ij}$ is completely arbitrary, while, in the latter, each item $j$ has a quality $q_j$ , each buyer $i$ has a value $v_i$ and the benefit $v_{ij}$ is defined as the product $v_i q_j$ . The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the problem cannot be approximated to a factor $O(m^{1-ε})$ , for any $ε>0$ , unless {\sf P} = {\sf NP} and that such result is asymptotically tight. In fact we provide a simple $m$ -approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of "proper" instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting $2$ -approximation algorithm and show that no $(2-ε)$ -approximation is possible for any $0<ε\leq 1$ , unless {\sf P} $=$ {\sf NP}. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.