1,721,007 research outputs found
A Branch-and-Cut Algorithm for the Maximum Cardinality Stable Set Problem
No full textWe propose a branch-and-cut algorithm for the Maximum Cardinality Stable Set problem. Rank constraints of general structure are generated by executing clique separation algorithms on a modified graph obtained with edge projections. A branching scheme exploiting the available inequalities is also introduced. A computational experience on the DIMACS benchmark graphs validates the effectiveness of the approach
Il Libro Bianco sulla Televisione Digitale Terrestre
No full textLa trasmissione digitale costituisce una
tappa di capitale importanza nello sviluppo
tecnologico dei sistemi televisivi.
Essa rappresenta il passaggio essenziale verso
la convergenza di informatica e telecomunicazioni
e consente di trasformare l’apparecchio
televisivo in una piattaforma per lo sviluppo dei
servizi interattivi, che si aggiungono così alla
funzione tradizionale di diffusione circolare dei
segnali. All'origine delle attività europee in questo
campo c’è il progetto Digital Video Broadcasting (DVB) promosso dalla Commissione
europea allo scopo di definire standard comuni.
Il progetto, cui hanno partecipato 170 società
coinvolte nei diversi settori dell'industria
televisiva, ha raggiunto l'obiettivo di stabilire un
unico standard condiviso su scala europea per
le trasmissioni televisive digitali via satellite
(DVB-S), via cavo (DVB-C) e via terra (DVB-T).
Questi standard sono stati ora adottati anche
dal Giappone e da altri paesi non europei
The Network Packing Problem in Terrestrial Broadcasting
No full textThe introduction of digital terrestrial broadcasting all over Europe requires a complete and challenging replanning of in-place analog systems. However, an abrupt migration of resources (transmitters and frequencies) from analog to digital networks cannot be accomplished because the analog services must be preserved temporarily. Hence, a multiobjective problem arises, in which several networks sharing a common set of resources have to be designed. This problem is referred to as the network packing problem. In Italy, this problem is particularly challenging because of a large number of transmitters, orographical features, and strict requirements imposed by Italian law. In this paper, we report our experience in developing solution methods at the major Italian broadcaster Radiotelevisione Italiana (RAI S.p.A.). We propose a two-stage heuristic. In the first stage, emission powers are assigned to each network separately. In the second stage, frequencies are assigned to all networks so as to minimize the loss from mutual interference. A software tool incorporating our methodology is currently in use at RAI to help discover and select high-quality alternatives for the deployment of digital equipment
A Competitive Scheduling Problem and its Relevance to UMTS Channel Assignment
No full textThis article investigates a two-user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunication System (UMTS) developed within the European IST project FUTURE: given two mobile terminals, one wants to maximize the on-time data packets transmitted to one user, while guaranteeing a certain amount of on-time data packets to the other. We show that the problem is NP-hard, despite peculiar properties of data and solutions. We propose a fast Lagrangian heuristic able to cope with a severe real-time requirement, and compare it to a greedy-like heuristic on a set of practical instances
Models and algorithms for terrestrial digital broadcasting
No full textThe service provided by a Digital Video Broadcasting (DVB) system in terms of coverage of territory and population is greatly affected by transmitters emission power and temporal offset. We show that the problem of computing the emission powers so as to guarantee the required signal to interference ratio can be formulated as a mixed integer linear program. We also model the optimization of temporal offsets as a maximum clique problem on interval graphs.
We analyze the behaviour of the models and verify their practical applicability in a computational experience on the whole Italian territory. Both the models allow to manage large scale instances and to achieve high coverage of population and territory
Strong lift-and-project cutting planes for the Stable Set Problem
No full textGiven a graph G = (V,E), QSTAB(G) denotes the polytope defined by the clique and non-negativity inequalities. The application of the Lovasz-Schrijver M(k,k) lifting operator to QSTAB(G) yields a strong non-compact linear relaxation of the stable set problem, as illustrated in Giandomenico et al.(2008). In particular, the upper bounds obtained by optimizing over M(QSTAB(G),QSTAB(G)) are comparable, sometimes better, than the Lovasz theta number \theta(G) as well as stronger bounds computed by semidefinite programming techniques (Burer, Vandenbussche 2006, Gruber and Rendl 2003, Dukanovic and Rendl 2007).
In this talk we illustrate the projection of M(QSTAB(G),QSTAB(G)) onto the original space by the Benders decomposition. An extensive computational experience is presented showing that the resulting cutting planes are effective and the method promising for practical implementations
- …
