<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-forward-container">
<p class="MsoNormal"><b>Estimados Académicos (as) y Alumnos(as)<br>
</b></p>
<p class="MsoNormal"><b>Se les recuerda que hoy miércoles 04 de
diciembre a las 14:30 hrs. se realizará el Seminario AGCO,
en Av República 701, Sala 22.<br>
</b></p>
<p class="MsoNormal"><b>Seminar AGCO </b></p>
<p><strong>Author: </strong>Matías Villagra, PUC</p>
<p><strong><span style="mso-ansi-language:EN-US" lang="EN-US">Where:</span></strong><span
style="mso-ansi-language:EN-US" lang="EN-US"> Av República
701,<strong> Sala 22</strong>.</span></p>
<p><strong><span style="mso-ansi-language:EN-US" lang="EN-US">When:</span></strong><span
style="mso-ansi-language:EN-US" lang="EN-US"> Wednesday,
December 4, <strong>14:30</strong>.</span></p>
<p><strong><span style="mso-ansi-language:EN-US" lang="EN-US">Title:</span></strong><span
style="mso-ansi-language:EN-US" lang="EN-US"> An efficient
symmetry breaking technique for arbitrary groups</span></p>
<p style="text-align:justify"><strong><span
style="mso-ansi-language: EN-US" lang="EN-US">Abstract: </span></strong><span
style="mso-ansi-language: EN-US" lang="EN-US"> Symmetries are
commonly found in Integer Linear Programs (ILPs) or in some of
their substructures. Having many symmetric solutions could
make common algorithms as branch-and-bound inefficient, hence
breaking symmetries might yield important gains.</span></p>
<p style="text-align:justify"><span
style="mso-ansi-language:EN-US" lang="EN-US">Given a group of
symmetries of an ILP, a Fundamental Domain is a set of R^n
that aims to select a unique representative of symmetric
vectors, i.e. such that each point in the set is a unique
representative under its G-orbit, effectively breaking all
symmetries of the group. The canonical Fundamental Domain
found in the literature, which can be constructed for any
permutation group, is NP-hard to separate even for very simple
groups, whose elements are disjoint involutions (Babai &
Luks 1983).</span></p>
<p style="text-align:justify"><span
style="mso-ansi-language:EN-US" lang="EN-US">In this talk I
will introduce basic group theoretical tools to show that for
every finite permutation group there exists a Fundamental
Domain which has quadratic many facets on the dimension, hence
the separation problem for this particular Fundamental Domain
can be done in polynomial time. Even more, this implies that
for a given group there exist different types of Fundamental
Domains, some of which can be separated in polytime while
others cannot. In particular, intersecting a given polytope
with different Fundamental Domains (for a fixed group), might
yield polytopes with radically different extension complexity.</span></p>
<p style="text-align:justify"><span
style="mso-ansi-language:EN-US" lang="EN-US">This is joint
work with José Verschae and Léonard von Niederhäusern.</span></p>
<p style="text-align:justify"><span
style="mso-ansi-language:EN-US" lang="EN-US">Esperando contar
con su presencia, les saluda, <br>
</span></p>
<p style="text-align:justify"><span
style="mso-ansi-language:EN-US" lang="EN-US">Ma. Inés Rivera <br>
</span></p>
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:-536870145 1107305727 0 0 415 0;}
@font-face
{font-family:Cambria;
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:-536870145 1073743103 0 0 415 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin-top:0cm;
margin-right:0cm;
margin-bottom:10.0pt;
margin-left:0cm;
line-height:115%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Cambria",serif;
mso-ascii-font-family:Cambria;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Cambria;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Cambria;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;
mso-fareast-language:EN-US;}
p
{mso-style-noshow:yes;
mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman",serif;
mso-fareast-font-family:"Times New Roman";}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-size:10.0pt;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Cambria",serif;
mso-ascii-font-family:Cambria;
mso-fareast-font-family:Cambria;
mso-hansi-font-family:Cambria;
mso-ansi-language:EN-US;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 3.0cm 70.85pt 3.0cm;
mso-header-margin:36.0pt;
mso-footer-margin:36.0pt;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
-->
</style> </div>
</body>
</html>