Search

The total matching polytope generalizes the stable set polytope and the matching polytope. In this paper, we first propose new facet-defining inequalities for the total matching polytope. We then give an exponential-sized, non-redundant description in the original space and a compact description in an extended space of the total matching polytope of complete bipartite graphs.

In the total matching problem, one is given a graph G with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incident union of a stable set and a matching. We consider the natural formulation of the problem as an integer program (IP), with variables corresponding to vertices and edges. Let M = M(G) denote the constraint matrix of this IP. We define Delta(G) as the maximum absolute value of the determinant of a square submatrix of M. We show that the total matching problem can be solved in strongly polynomial time provided Delta(G) <= Delta for some constant Delta is an element of Z(>= 1). We also show that the problem of computing Delta(G) admits an FPT algorithm. We also establish further results on Delta(G) when G is a forest.

In this paper, we propose an integer linear programming model whose solutions are the aperiodic rhythms tiling with a given rhythm A. We show how it can be used to define an iterative algorithm that, given a period n, finds all the rhythms which tile with a given rhythm A and also to efficiently check the necessity of the Coven-Meyerowitz condition (T2). To conclude, we run several experiments to validate the time efficiency of the model.

Un matching totale di un grafo G = (V,E) è un sottoinsieme di G tale che i suoi elementi, cioè vertici e spigoli, sono a coppie non adiacenti. In questo contesto, il Total Matching Problem richiede di trovare un matching totale di dimensione massima. Questo problema è stato principalmente studiato in letteratura da un punto di vista della teoria dei grafi. Tuttavia, a causa del forte collegamento con noti problemi combinatorici dello Stable Set Problem e del Matching Problem, il problema viene trattato da un punto di vista tipico della programmazione intera. In questa Tesi, viene presentato un approccio poliedrale al Total Matching Problem, e quindi, si introduce il corrispondente politopo, ovvero il Total Matching Polytope. Al meglio della nostra conoscenza, tale problema non è stato ancora affrontato da una prospettiva poliedrale. Vengono introdotte diverse famiglie di disuguaglianze valide: disuguaglianze vertex-clique basate su disuguaglianze di clique del politopo dell'insieme stabile, disuguaglianze di cicli congruent-2k3 cycles basate sulla parità dell'insieme dei vertici indotte dal ciclo, disuguaglianze even-clique indotte da sottografi completi di ordine pari e, balanced e non lifted balanced disuguaglianze bicliques basate su grafi bipartiti completi, dove la famiglia bilanciata ha la partizione degli insiemi di vertici di uguale dimensione, mentre la seconda classe ha ogni partizione di vertice di dimensioni diverse. Si dimostra che le disuguaglianze di ciclo congruent-2k3 sono faccette quando k = 4, e per grafi cubici, in determinate condizioni. Le non balanced lifted biclique disuguaglianze sono ottenute mediante una procedura di lifting e definiscono le faccette per grafi bipartiti. Mentre le clique di vertice, le even clique e le balanced bicliques definiscono sempre faccette. Inoltre, una prima descrizione lineare completa viene fornita per alberi e grafi bipartiti completi. Per quest'ultima famiglia, la caratterizzazione completa si ottiene pr, A total matching of a graph G = (V, E) is a subset of G such that its elements, i.e. vertices and edges, are pairwise not adjacent. In this context, the Total Matching Problem calls for a total matching of maximum size. This problem has been mainly studied in the literature from a graph theoretical point of view. However, due to the strong connection with well-known combinatorial problems of the Stable Set Problem and the Matching Problem, we focus on an integer programming point of view. In this Thesis, we present a polyhedral approach to the Total Matching Problem, and hence, we introduce the corresponding polytope, namely the Total Matching Polytope. To the best of our knowledge, we are the first to tackle the problem from a polyhedral perspective. We introduce several families of valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, even-clique inequalities induced by complete subgraphs of even order, and, balanced and non-balanced lifted biclique inequalities based on complete bipartite graphs, where the balanced family has the partition of the vertex sets of equal-size, whereas for the second class each vertex partition has different size. We prove that congruent-2k3 cycle inequalities are facet-defining when k = 4, and for cubic graphs, under certain conditions. The non-balanced lifted biclique inequalities are obtained by a lifting procedure and are facet-defining for bipartite graphs. While the vertex-clique, even-clique, and balanced biclique inequalities are always facet-defining. In addition, we provide a first linear complete description for Trees and Complete Bipartite Graphs. For the latter family, the complete characterization is obtained by projecting a higher-dimension polytope onto the original space. This leads to also give an extended formulation of small size for the Total Matching Polytope of C

A total coloring of a graph G=(V,E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the elements of G into total matchings, which are defined as subsets of vertices and edges that can take the same color. In this paper, we propose Integer Linear Programming models for both the Total Coloring and the Total Matching problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Hence, we study the Total Matching Polytope. We introduce three families of nontrivial valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, and even-clique inequalities induced by complete subgraphs of even order. We prove that congruent-2k3 cycle inequalities are facet-defining only when k=4, while the vertex-clique and even-cliques are always facet-defining. Finally, we present preliminary computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem.

In Mathematical Music theory, the Aperiodic Tiling Complements Problem consists in finding all the possible aperiodic complements of a given rhythm A. The complexity of this problem depends on the size of the period n of the canon and on the cardinality of the given rhythm A. The current state-of-the-art algorithms can solve instances with n smaller than 180. In this paper we propose an ILP formulation and a SAT Encoding to solve this mathemusical problem, and we use the Maplesat solver to enumerate all the aperiodic complements. We validate our SAT Encoding using several different periods and rhythms and we compute for the first time the complete list of aperiodic tiling complements of standard Vuza rhythms for canons of period n= { 180, 420, 900 }.

In a proper edge-coloring of a cubic graph an edge uv is called poor or rich, if the set of colors of the edges incident to u and v contains exactly three or five colors, respectively. An edge-coloring of a graph is normal, if any edge of the graph is either poor or rich. In this note, we show that some snarks constructed by using a method introduced by Loupekhine admit a normal edge-coloring with five colors. The existence of a Berge-Fulkerson Covering for a part of the snarks considered in this paper was recently proved by Manuel and Shanthi (2015). Since the existence of a normal edge-coloring with five colors implies the existence of a Berge-Fulkerson Covering, our main theorem can be viewed as a generalization of their result.

The widely accepted importance of energy efficiency in the building sector is continuously acknowledged by the engineering and research community, as proven by the quantity and diversification of relevant modeling proposals in literature. It is often difficult to collect and assess this plethora of approaches and sometimes the diversity of the features of the available options makes it hard to decide what is the most convenient for the purpose required. This work presents a comprehensive analysis of the most important results today, along with their various classification and assessment approaches for modeling energy building consumption. A critical review of the limitations of the different existing approaches is conducted, and open research challenges are also highlighted. Finally, a horizontal and selective assessment of their suitability according to a descriptive set of qualitative comparison contexts and parameters is provided. © 2017

Aims. Future astrophysics and cosmic microwave background space missions operating in the far-infrared to millimetre part of the spectrum will require very large arrays of ultra-sensitive detectors in combination with high multiplexing factors and efficient low-noise and low-power readout systems. We have developed a demonstrator system suitable for such applications. Methods. The system combines a 961 pixel imaging array based upon Microwave Kinetic Inductance Detectors (MKIDs) with a readout system capable of reading out all pixels simultaneously with only one readout cable pair and a single cryogenic amplifier. We evaluate, in a representative environment, the system performance in terms of sensitivity, dynamic range, optical efficiency, cosmic ray rejection, pixel-pixel crosstalk and overall yield at an observation centre frequency of 850 GHz and 20% fractional bandwidth. Results. The overall system has an excellent sensitivity, with an average detector sensitivity (NEPdet) =3 × 10-19 W/Hz measured using a thermal calibration source. At a loading power per pixel of 50 fW we demonstrate white, photon noise limited detector noise down to 300 mHz. The dynamic range would allow the detection of ~1 Jy bright sources within the field of view without tuning the readout of the detectors. The expected dead time due to cosmic ray interactions, when operated in an L2 or a similar far-Earth orbit, is found to be <4%. Additionally, the achieved pixel yield is 83% and the crosstalk between the pixels is <-30 dB. Conclusions. This demonstrates that MKID technology can provide multiplexing ratios on the order of a 1000 with state-of-the-art single pixel performance, and that the technology is now mature enough to be considered for future space based observatories and experiments., Tera-Hertz Sensing, QN/Quantum Nanoscience, QN/Gao Lab

Nested or intersecting surfaces are proven techniques for visualizing shape differences between static 3D objects (Weigle and Taylor II, IEEE Visualization, Proceedings, pp. 503–510, 2005). In this paper we present an image-based formulation for these techniques that extends their use to dynamic scenarios, in which surfaces can be manipulated or even deformed interactively. The formulation is based on our new layered rendering pipeline, a generic image-based approach for rendering nested surfaces based on depth peeling and deferred shading. We use layered rendering to enhance the intersecting surfaces visualization. In addition to enabling interactive performance, our enhancements address several limitations of the original technique. Contours remove ambiguity regarding the shape of intersections. Local distances between the surfaces can be visualized at any point using either depth fogging or distance fields: Depth fogging is used as a cue for the distance between two surfaces in the viewing direction, whereas closest-point distance measures are visualized interactively by evaluating one surface’s distance field on the other surface. Furthermore, we use these measures to define a three-way surface segmentation, which visualizes regions of growth, shrinkage, and no change of a test surface compared with a reference surface. Finally, we demonstrate an application of our technique in the visualization of statistical shape models. We evaluate our technique based on feedback provided by medical image analysis researchers, who are experts in working with such models., Intelligent Systems, Electrical Engineering, Mathematics and Computer Science

Imaging Science and Technology, Applied Sciences

Item does not contain fulltext, HYPOTHESIS: The goal of this study is to analyze the 3-dimensional anatomy of the cochlear spiral and to investigate the consequences of its course to insertion trauma during cochlear implantation. BACKGROUND: Insertion trauma in cochlear implant surgery is a feared surgical risk, potentially causing neural degeneration and altered performance of the implant. In literature, insertion trauma is reported to occur at specific locations. This has been ascribed to surgical technique and electrode design in relation to the size of the scala tympani. This study investigates whether there is an underlying anatomic substrate serving as a potential source for insertion trauma at these specific locations. METHODS: The 3-dimensional path of the cochlear spiral of 8 human temporal bones was determined by segmentation, skeletonization, distance mapping, and wave propagation technique applied on microcomputer tomography images. Potential pressure points along this path were estimated with linear regression. RESULTS: The cochlear lumen shows a noncontinuous spiraling path leading to potential pressure points during cochlear implantation at the basilar membrane in the region of 180 to 225 (12-14 mm) and 725 degrees (22-26 mm) and at the floor of the scala tympani around 0 to 90, 225 to 270, and 405 to 450 degrees. CONCLUSION: Our data favor the idea that the intrinsic 3-dimensional cochlear morphology contributes to the risk for insertion trauma during cochlear implantation at specific locations.