[Todos] Charla: A Multiple Traveling Salesman Problem: testing of digital microfluidic biochips

[Irene Loiseau]

Invitamos a la conferencia que se dictará el martes 10 de marzo
a las 14 y 30hrs en el Pabellón I, Ciudad Universitaria (aula E 24) sobre

"A Multiple Traveling Salesman Problem: Optimal Testing of Digital
Microfluidic Biochips"

Conferencista: Robert Garfinkel, School of Business, University of
Connecticut
http://www.business.uconn.edu/cms/p461/u34/r0/mr

Coautores:
- Ion Mandoiu, Computer Science Department, University of Connecticut -
Bogdan Pasaniuc, International Computer Science Institute, UC Berkeley -
Alexander Zelikovsky, Department of Computer Science, Georgia State
University

Abstract:
Digital microfluidic biochips are used for performing biochemical analyses
by manipulating droplets on a rectangular array of electrodes.  Detection
of defective electrodes or connections between cells of the chip, is done
by routing droplets along paths covering all electrodes or connections and
checking their arrivals at a sink.  Using multiple test droplets can
reduce test time, but requires coordination to avoid droplet interference.
 The problem is to determine the optimal number of droplets and their
paths in order to minimize completion time.

When the chip is empty, the complete structure of an optimal solution can
be determined in advance. However, given arbitrary assay distributions on
the chip, the optimization problem for cell visitation is shown to be
NP-Hard.

Formulations, exact and heuristic algorithms, theoretical bounds, and
computational results are given.


---------------------------------------------------
Irene Loiseau
Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
Pabellón I- Ciudad Universitaria
1428 Buenos Aires - ARGENTINA
TE/FAX: 54 11 4576 3359
TE: 54 11 4576 3390/96 int 711
e-mail: irene en dc.uba.ar

_______________________________________________
Docentes mailing list
Docentes en dc.uba.ar
https://listas.dc.uba.ar/cgi-bin/mailman/listinfo/docentes