459 research outputs found
Ricerca di strutture speciali in problemi di programmazione lineare intera
No full textI problemi di Programmazione Lineare Intera sono in generale notoriamente
difficili da trattare sotto l’aspetto computazionale. La progettazione di algoritmi
efficienti per problemi di tale natura, quindi, spesso trae grande vantaggio
dallo studio della struttura matematica soggiacente. Prendendo come spunto
il problema di determinare una sottomatrice massima di tipo network di una
matrice a valori in {0,−1, 1}, nel lavoro di tesi si analizza il problema equivalente
di bilanciamento di un grafo signed (mbs, Max Balanced Subgraph)
e quindi si generalizzano alcuni dei risultati ottenuti a problemi combinatorici
di più ampia portata.
In particolare, lo studio ha portato all’ideazione e implementazione dell’euristica
CCH (Cycle-Contraction Heuristic) per il problema mbs che è risultata
più efficace delle euristiche esistenti in letteratura. L’algoritmo CCH è basato
su una regola originale di trasformazione e semplificazione dei grafi che ne riduce
progressivamente la lunghezza dei cicli senza per questo compromettere
l’ammissibilità delle soluzioni determinate sul grafo modificato.
Successivamente sono state ideate delle regole originali di data reduction che
hanno lo scopo di semplificare le istanze e/o ridurne la dimensione, pur conservando
su esse la soluzione ottima del problema. Con queste regole, le performance
dell’euristica CCH sono migliorate sia in termini di efficienza che di
efficacia.
Nella tesi viene poi proposto un nuovo modello esatto per il problema mbs
basato sulla trasformazione di un grafo signed in un grafo semplice detto 2-
layer, stabilendo una stretta connessione tra il problema mbs e il più comune
problema di massimo insieme stabile (mis). Il grafo 2-layer fornisce nuovi
strumenti per progettare algoritmi per il problema mbs, basati sui numerosi
metodi di soluzione (esatti o euristici) adottati per il problema mis.
Infine, è stato affrontato il tema della generalizzazione di alcuni problemi
combinatorici su grafi signed ed è stato esteso il modello 2-layer al modello
k-layer. In particolare è stato provato che il problema di k-coloring di un grafo
signed - che generalizza il problema di bilanciamento di un grafo signed e quello
di bipartizione di un grafo semplice - equivale al problema mis sul grafo k-layer
A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
No full textA signed graph, i.e., an undirected graph whose edges have labels in {-1,+1}, is balanced if it has no negative cycles. Given a signed graph, we are interested in a balanced induced subgraph of maximum order (the MBIS problem). In the present work, we propose a greedy approach for the MBIS problem that is based on the progressive shortening of negative cycles, and that generalizes the well-known minimum-degree greedy heuristic for the maximum independent set problem. An extensive computational study on three classes of instances shows that the new algorithm outperforms the reference heuristics proposed in the literature
Succinctness of descriptions of SBTA-languages
No full textAbstractSystolic binary tree automata (SBTA) provide a basic and robust model for one-way parallel computations on binary tree networks of memoryless processors. In this paper we investigate succinctness of descriptions of languages accepted by SBTA, measured in terms of the number of states of minimal SBTA. We study the problem in different settings. First we provide various criteria to determine lower bounds on the state-complexity of an SBTA-language L, that is bounds on the minimum number of states for an SBTA to accept L, and we show the existence of dense hierarchies of families of SBTA-languages with respect to their state-complexity. We study then how much Boolean operations can contribute to the increase of the state-complexity of SBTA-languages and we provide tight bounds on the complexity of languages obtained by union, intersection and complement of SBTA-languages. Finally, we consider different but equivalent models of SBTA and determine bounds on the trade-off between the state-complexity of a language L for any two equivalent models of SBTA. Moreover, we compare the state-complexity of regular languages with respect to their description by deterministic finite automata and several types of SBTA.We conclude the paper with a brief discussion on the minimization problem of SBTA and with some open problems
Games, Automata, Logic, and Formal Verification (GandALF 2010) Special Issue - Editorial
No full text
La triptasi sierica nella diagnosi di mastocitosi sistemica in pazienti adulti senza lesioni cutanee
No full textBackground.: Mastocytosis is a rare disease characterized by clonal proliferation of mast cells in several organs, such as bone marrow, liver, spleen, skin, gastrointestinal tract and lymph nodes. The course of disease and the prognosis are variable. The typical skin lesion of mastocytosis is characterized by red to brown macules, known as urticaria pigmentosa (UP). However, in about 10–30% of patients, mastocytosis occurs in absence of typical skin lesions; in these patients, the clinical picture is mainly determined by mediator-related symptoms, such as urticaria, flushing, diarrhea and recurrent anaphylaxis. Thus, in patients without skin lesions, diagnosis of mastocytosis could be difficult. The determination of serum tryptase could be useful to improve diagnostic accuracy. Methods.: In our cohort of 67 patients (44 females and 23 males; mean age 28 years) with systemic mastocytosis (SM) we selected those without skin lesion and we evaluated their initial clinical features. The diagnosis of SM was made by bone marrow biopsy according the WHO criteria. Serum tryptase levels were determined using Phadia ImmunoCAP methodology and the analytical system Phadia 250 (Thermo Fisher Scientific, Waltham, MA, USA). Results.: Fifteen percent (10/67) of our patients with systemic mastocytosis have no skin lesions. Five of them are males (mean age: 55 years). The majority of patients (7/10) have ISM, one has a bone marrow mastocytosis (BMM), one has systemic mastocytosis associated to not clonal mast cells disorders (SM-AHNMD), and one has advanced systemic mastocytosis (ASM). The most frequent presenting symptom in these patients (4 out of 10) was pathological vertebral fracture due to severe osteoporosis. Other patients had severe anaphylaxis, progressive peripheral monocytosis and bone pain. In only one case the diagnosis was incidental, because bone marrow biopsy was done to confirm another diagnosis (essential thrombocythemia). In all cases, elevation of serum tryptase suggested the diagnosis of systemic mastocytosis. The values of tryptase in these patients ranged from 15 to 120 μg/L with a mean of 52 μg/L (normal range: up to 11.4 μg/L). Conclusions.: In patients without skin lesions, the diagnosis of mastocytosis could be challenging. The clinical presentations of mastocytosis are heterogeneous, ranging from severe clinical pictures of osteoporosis to hematologic abnormality in otherwise asymptomatic patients. Our data indicate that the diagnostic relevance of serum tryptase levels in patients without skin lesions, but with suspicious symptoms and/or signs of SM, and its utility in selecting patients who do need a bone marrow biopsy
- …
