An integer programming model for the minimum interval graph completion problem

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), finding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.

A Bayesian Semiparametric Approach for Solving the Discrete Calibration Problem

In this article, we introduce a semi-parametric Bayesian approach based on Dirichlet process priors for the discrete calibration problem in binomial regression models. An interesting topic is the dosimetry problem related to the dose-response model. A hierarchical formulation is provided so that a Markov chain Monte Carlo approach is developed. The methodology is applied to simulated and real data.

The Two-Interval Line-Segment Problem

In this paper, the NPMLE in the one-dimensional line segment problem is defined and studied, where line segments on the real line through two non-overlapping intervals are observed. The self-consistency equations for the NPMLE are defined and a quick algorithm for solving them is provided. Supnorm weak convergence to a Gaussian process and efficiency of the NPMLE is proved. The problem has a strong geological application in the study of the lifespan of species.

Algorithms and cryptographic protocols using elliptic curves

En els darrers anys, la criptografia amb corbes el.líptiques ha adquirit una importància creixent, fins a arribar a formar part en la actualitat de diferents estàndards industrials. Tot i que s'han dissenyat variants amb corbes el.líptiques de criptosistemes clàssics, com el RSA, el seu màxim interès rau en la seva aplicació en criptosistemes basats en el Problema del Logaritme Discret, com els de tipus ElGamal. En aquest cas, els criptosistemes el.líptics garanteixen la mateixa seguretat que els construïts sobre el grup multiplicatiu d'un cos finit primer, però amb longituds de clau molt menor. Mostrarem, doncs, les bones propietats d'aquests criptosistemes, així com els requeriments bàsics per a que una corba sigui criptogràficament útil, estretament relacionat amb la seva cardinalitat. Revisarem alguns mètodes que permetin descartar corbes no criptogràficament útils, així com altres que permetin obtenir corbes bones a partir d'una de donada. Finalment, descriurem algunes aplicacions, com són el seu ús en Targes Intel.ligents i sistemes RFID, per concloure amb alguns avenços recents en aquest camp.

Limited-sampling strategy models for estimating the pharmacokinetic parameters of 4-methylaminoantipyrine, an active metabolite of dipyrone

Bioanalytical data from a bioequivalence study were used to develop limited-sampling strategy (LSS) models for estimating the area under the plasma concentration versus time curve (AUC) and the peak plasma concentration (Cmax) of 4-methylaminoantipyrine (MAA), an active metabolite of dipyrone. Twelve healthy adult male volunteers received single 600 mg oral doses of dipyrone in two formulations at a 7-day interval in a randomized, crossover protocol. Plasma concentrations of MAA (N = 336), measured by HPLC, were used to develop LSS models. Linear regression analysis and a "jack-knife" validation procedure revealed that the AUC0-¥ and the Cmax of MAA can be accurately predicted (R²>0.95, bias <1.5%, precision between 3.1 and 8.3%) by LSS models based on two sampling times. Validation tests indicate that the most informative 2-point LSS models developed for one formulation provide good estimates (R²>0.85) of the AUC0-¥ or Cmax for the other formulation. LSS models based on three sampling points (1.5, 4 and 24 h), but using different coefficients for AUC0-¥ and Cmax, predicted the individual values of both parameters for the enrolled volunteers (R²>0.88, bias = -0.65 and -0.37%, precision = 4.3 and 7.4%) as well as for plasma concentration data sets generated by simulation (R²>0.88, bias = -1.9 and 8.5%, precision = 5.2 and 8.7%). Bioequivalence assessment of the dipyrone formulations based on the 90% confidence interval of log-transformed AUC0-¥ and Cmax provided similar results when either the best-estimated or the LSS-derived metrics were used.

« Resolution Search » et problèmes d’optimisation discrète

Thèse réalisée en cotutelle avec l'Université d'Avignon.

Computations in Relative Algebraic K-Groups

Let G be finite group and K a number field or a p-adic field with ring of integers O_K. In the first part of the manuscript we present an algorithm that computes the relative algebraic K-group K_0(O_K[G],K) as an abstract abelian group. We solve the discrete logarithm problem, both in K_0(O_K[G],K) and the locally free class group cl(O_K[G]). All algorithms have been implemented in MAGMA for the case K = \IQ. In the second part of the manuscript we prove formulae for the torsion subgroup of K_0(\IZ[G],\IQ) for large classes of dihedral and quaternion groups.

Características das Curvas de Regressão da Gonadotrofina Coriônica Pós-mola Hidatiforme Completa

Objetivos: construir a curva de regressão do b-hCG pós-mola hidatiforme completa (MHC) com remissão espontânea e comparar com a curva de regressão pós-MHC com tumor trofoblástico gestacional (TTG). Análise comparativa da curva de regressão do b-hCG das portadoras de MHC, acompanhadas no Serviço, com a curva de regressão observada por outros autores1-3. Métodos: foi realizada avaliação clínica e laboratorial (dosagem sérica de b-hCG), na admissão e no segmento pós-molar, de todas as pacientes com MHC, atendidas entre 1990 e 1998 no Hospital das Clínicas de Botucatu - Unesp. O resultado da determinação seriada do b-hCG foi analisado em curvas log de regressão. A evolução da curva de regressão do b-hCG foi analisada e comparada em MHC com remissão espontânea e MHC com TTG numa curva log de regressão, com intervalo de confiança de 95%. A curva log de regressão do grupo de remissão espontânea foi comparada com curvas consideradas padrão1,2. Foram construídas curvas log individuais de todas as pacientes e classificadas de acordo com os quatro tipos de curva (I, II, III e IV), propostos para o seguimento pós-molar³. Resultados: 61 pacientes com MHC tiveram seguimento pós-molar completo, 50 (82%) apresentaram remissão espontânea e 11 (18%) desenvolveram TTG. No grupo de pacientes com MHC e remissão espontânea, o tempo para alcançar a normalização dos níveis do b-hCG, após o esvaziamento molar, foi até 20 semanas. As pacientes que desenvolveram TTG apresentaram desvio precoce da curva de regressão normal do b-hCG, 4 a 6 semanas após o esvaziamento molar. Nestas pacientes, a quimioterapia foi introduzida em média na 9ª semana pós-esvaziamento molar. Conclusões: a curva de regressão do b-hCG pós-MHC com remissão espontânea apresentou declínio log exponencial, semelhante ao observado por outros autores1,2, e diferente das MHC com TTG. Foram identificados três tipos de curvas de regressão do b-hCG, semelhantes aos de Goldstein³, I, II e IV, e outros dois tipos diferentes de regressão do b-hCG: V (regressão normal) e VI (regressão anormal).

Stochastic scheduling - A flow shop no wait application and solutions

Minimizing the makespan of a flow-shop no-wait (FSNW) schedule where the processing times are randomly distributed is an important NP-Complete Combinatorial Optimization Problem. In spite of this, it can be found only in very few papers in the literature. By considering the Start Interval Concept, this problem can be formulated, in a practical way, in function of the probability of the success in preserve FSNW constraints for all tasks execution. With this formulation, for the particular case with 3 machines, this paper presents different heuristics solutions: by integrating local optimization steps with insertion procedures and by using genetic algorithms for search the solution space. Computational results and performance evaluations are commented. Copyright (C) 1998 IFAC.

Criptografia e curvas elípticas

Pós-graduação em Matemática Universitária - IGCE

Incerteza intervalar em otimização e controle

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

The Performance of Elliptic Curve Based Group Diffie-Hellman Protocols for Secure Group Communication over Ad Hoc Networks

The security of the two party Diffie-Hellman key exchange protocol is currently based on the discrete logarithm problem (DLP). However, it can also be built upon the elliptic curve discrete logarithm problem (ECDLP). Most proposed secure group communication schemes employ the DLP-based Diffie-Hellman protocol. This paper proposes the ECDLP-based Diffie-Hellman protocols for secure group communication and evaluates their performance on wireless ad hoc networks. The proposed schemes are compared at the same security level with DLP-based group protocols under different channel conditions. Our experiments and analysis show that the Tree-based Group Elliptic Curve Diffie-Hellman (TGECDH) protocol is the best in overall performance for secure group communication among the four schemes discussed in the paper. Low communication overhead, relatively low computation load and short packets are the main reasons for the good performance of the TGECDH protocol.

MATHEMATICAL MODELS AND POLYHEDRAL STUDIES FOR INTEGRAL SHEET METAL DESIGN

We deal with the optimization of the production of branched sheet metal products. New forming techniques for sheet metal give rise to a wide variety of possible profiles and possible ways of production. In particular, we show how the problem of producing a given profile geometry can be modeled as a discrete optimization problem. We provide a theoretical analysis of the model in order to improve its solution time. In this context we give the complete convex hull description of some substructures of the underlying polyhedron. Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

A public key cryptosystem based on block upper triangular matrices

We propose a public key cryptosystem based on block upper triangular matrices. This system is a variant of the Discrete Logarithm Problem with elements in a finite group, capable of increasing the difficulty of the problem while maintaining the key size. We also propose a key exchange protocol that guarantees that both parties share a secret element of this group and a digital signature scheme that provides data authenticity and integrity.