ETC - VIII Encontro de Teoria da Computação
O Encontro de Teoria da Computação, em sua oitava edição, tem se apresentado como um fórum voltado para a grande área de Teoria da Computação, proposto por membros da Comissão Especial em Algoritmos, Combinatória e Otimização (CE-ACO), com objetivo de promover uma maior divulgação da área para a comunidade brasileira de computação e afins, através do principal evento da SBC, o CSBC.
Esse evento é voltado primeiramente para alunos em formação, mas também visa a proporcionar uma maior integração entre os pesquisadores e profissionais que atuam na área, seja com enfoque em teoria pura, seja em aplicações, estimulando a discussão da importância dos fundamentos da computação e sua aplicação direta no entendimento e resolução de problemas das mais diversas áreas e segmentos de mercado.
Convidamos a comunidade a compartilhar resultados de pesquisa por meio da submissão de resumos estendidos, abrangendo tanto pesquisas em nível de pós-graduação como também iniciação científica na graduação.
O evento é aberto para a comunidade, com especial interesse nos alunos em formação de graduação e de pós-graduação.
Convidamos a comunidade científica, em particular àqueles atuando na área de teoria da computação e áreas correlatas, a submeterem seus resultados de pesquisa, por meio de resumos estendidos, ao VIII Encontro de Teoria da Computação, evento satélite do Congresso da Sociedade Brasileira de Computação (CSBC). Trabalhos envolvendo alunos de pós-graduação ou graduação são especialmente bem-vindos. Os trabalhos selecionados deverão ser apresentados oralmente em sessões técnicas do ETC 2023.
Os tópicos de interesse incluem, mas não são limitados a:
- Algoritmos: análise e projeto de algoritmos, algoritmos exatos, algoritmos de aproximação, algoritmos probabilísticos, algoritmos parametrizados, algoritmos online, técnicas de decomposição e balanceamento, algoritmos distribuídos e paralelos.
- Complexidade Computacional: análise de problemas e algoritmos, NP-completude, reduções polinomiais, inaproximabilidade, classes de complexidade de tempo e espaço, complexidade parametrizada, análise amortizada, abordagens lógicas à complexidade computacional, aplicações.
- Computabilidade: modelos teóricos de computação, métodos e linguagens formais, autômatos, computabilidade de Turing e generalizações, teoria da prova, teoria da recursão, reduções, decidibilidade, definibilidade, conjuntos enumeráveis, sistemas de provas interativas, matemática reversa, redes de Petri, aplicações.
- Otimização Combinatória: otimização em redes, programação dinâmica, estruturas combinatórias, combinatória poliédrica, métodos exatos e aproximativos, métodos de busca global e de busca local, heurísticas, modelagem e aplicações.
- Programação Matemática: programação linear inteira e não-linear, programação multiobjetivo, programação por restrições, otimização estocástica, otimização robusta, formulações, decomposições, métodos de solução exatos, heurísticos e híbridos.
- Teoria dos Grafos e Combinatória: problemas clássicos, caracterização estrutural, reconhecimento, classes de grafos, estruturas proibidas, desenho e layout de grafos, teoria espectral, teoria extremal, grafos aleatórios, algoritmos, complexidade, aplicações.
- Teoria da Informação, Números e Criptografia: fundamentos, compressão, teoria de códigos, corretores de erro, codificação de fonte, sistemas numéricos, aritmética modular, congruências, divisibilidade, criptoanálise, protocolos com segurança demonstrável, algoritmos, aplicações.
- Teoria dos Jogos e da Decisão: fundamentos, sistemas em equilíbrio, equilíbrio de Nash, dominância, preço da anarquia e da estabilidade, leilões e mecanismos, precificação, estratégias competitivas, jogos cooperativos, jogos combinatórios, pesquisa operacional, algoritmos, aplicações.
- Geometria Computacional: algoritmos e estruturas de dados para problemas geométricos estáticos e cinéticos, espaços métricos, geometria de distâncias, estruturas baseadas em propriedades geométricas, estruturas espaciais, aplicações.
- Aplicações e Problemas Práticos: alocação de recursos, apoio à tomada de decisão, biologia computacional, compiladores, economia, escalonamento, engenharias, estrutura molecular, pesquisa operacional, probabilidade e estatística, processos produtivos, reconhecimento de padrões, redes de computadores, redes complexas, redes livres de escala e redes web, robótica, roteamento, segurança de código, sistemas e redes, sistemas paralelos e distribuídos, teoria de conjuntos, visualização de dados, aplicações com grandes massas de dados, aplicações dinâmicas, aplicações de tempo real.
Formato dos artigos
Os trabalhos devem ser submetidos na forma de resumos estendidos, elaborados preferencialmente em LaTeX, seguindo o formato de artigos da SBC, disponível em http://tinyurl.com/sbc-template-artigos. Devem ter no máximo 04 (quatro) páginas, sem incluir as referências.
O artigo poderá ter opcionalmente um apêndice, fora do limite de 4 páginas, contendo material de apoio adicional (como provas, detalhes de implementação ou experimentos computacionais), que não puderam ser incluídos no artigo submetido. O apêndice poderá ser usado para fins de avaliação do trabalho, mas não fará parte do texto publicado nos anais em caso de aceitação do artigo.
Meio de submissão
A submissão dos artigos será eletrônica, em formato PDF, e será feita por meio do sistema JEMS a partir do link https://jems.sbc.org.br/etc2023.
Processo de revisão
O trabalho submetido será revisado com método single-blind por pelo menos dois revisores, sejam membros do comitê de programa ou pesquisadores por eles indicados.
- Limite para submissão dos trabalhos:
05/03/2023–20/03/2023– 05/04/2023 (Final) - Notificação dos trabalhos selecionados:
05/05– 20/05/2023 - Data limite para envio das versões finais dos trabalhos:
16/05– 28/05/2023 - Prazo de inscrição autores(as):
16/05– 05/07/2023
Para que um artigo aceito seja apresentado e incluído nos anais do evento, é necessário que ao menos um dos autores do artigo realize a sua inscrição no evento. Cada inscrição na categoria profissional dá direito à publicação de um único artigo, considerando qualquer um dos eventos-base ou eventos-satélite do CSBC. Autores com mais de um artigo aprovado em qualquer evento do CSBC deverão pagar uma “taxa de publicação” por artigo adicional. O valor dessa taxa pode ser visto na página de inscrições do CSBC 2023.
Os artigos aceitos serão publicados na SBC Open Lib, a biblioteca digital da SBC, na série Anais do Encontro de Teoria da Computação (ETC) disponível em https://sol.sbc.org.br/index.php/etc. Todos os artigos serão indexados com DOI.
Os resumos estendidos submetidos ao ETC 2023 estarão automaticamente concorrendo ao prêmio de melhor trabalho do evento, que será escolhido por uma comissão especialmente designada para esse fim, composta por pelo menos três membros. A comissão levará em conta as avaliações dos revisores, além de sua própria análise dos trabalhos.
| ETC 2023 | ||
| SEGUNDA | Sala | |
| 09:00 – 09:15 | Carapibus | Abertura |
| 09:15 – 10:05 | Carapibus | Palestra do Anand Subramanian: Hybrid iterated local search frameworks for classes of combinatorial optimization problems (Chair: Manoel Campêlo) |
| 10:05 – 10:30 A | Carapibus | Um QPTAS para o Problema de Empacotamento de Cı́rculos em Linha* (Elisa Dell Arriva, Flavio Miyazawa) (Chair: Manoel Campêlo) |
| 10:05 – 10:30 B | Tabatinga | Novos resultados sobre coloração de arestas em grafos split: grafos split minimamente 3-admissíveis (Diego Ferraz, Sulamita Klein, Fernanda Couto) (Chair: Guilherme Gomes) |
| 10:30 – 11:00 | COFFEE BREAK | |
| 11:00 – 11:25 A | Carapibus | PTAS para Problema do Empacotamento Soma Mínima com Quadrados* (Rachel Vanucchi Saraiva, Rafael Schouery) (Chair da sessão: Rafael Schouery) |
| 11:25 – 11:50 A | Carapibus | Algoritmos de Aproximação para o Problema de Extensão de Quadrados Latinos Diagonais* (Vítor Chagas, Flavio Miyazawa) |
| 11:50 – 12:15 A | Carapibus | Complexidade parametrizada do problema de reconfiguração de separadores* (Guilherme de Castro Mendes Gomes, Vinicius dos Santos) |
| 11:00 – 11:25 B | Tabatinga | Controlando o fogo nos fulerenos (Sérgio Fusquino, Diana Sasaki, Diego Nicodemos) (Chair da sessão: Diana Sasaki) |
| 11:25 – 11:50 B | Tabatinga | Nota sobre o tempo mínimo de infecção em 2-neighbour bootstrap percolation em grids partindo de n+1 vértices (Matheus Pascoal, Fabricio Benevides) |
| 11:50 – 12:15 B | Tabatinga | Modelo para Detecção de Plágio em Exercícios de Programação na Linguagem Python (Rafael Chaves, Kerven Albuquerque, Thiago Gouveia da Silva, Renato Chaves) |
| 12:30 – 14:00 | ALMOÇO | |
| 14:00 – 14:50 | Carapibus | Homenagem ao Nelson Maculan (chair: Lucidio Formiga) |
| 14:55 – 15:20 A | Carapibus | Um algoritmo genético híbrido para o problema do caixeiro viajante com tempos de liberação* (Gabriel Soares, Teobaldo Bulhões Júnior, Bruno Bruck) (Chair da sessão: Carla Lintzmayer) |
| 15:20 – 15:45 A | Carapibus | MIP-Heuristics for the Capacitated Lot-Sizing with Hybrid Flow Shop Integration* (Diego Silva, Geraldo Robson Mateus) |
| 15:45 – 16:10 A | Carapibus | Decomposição de Fluxos em Digrafos Arco-Coloridos* (Cláudio Carvalho Neto, Claudia Linhares Sales, Jonas Silva, Karolinna Maia) |
| 16:10 – 16:35 A | Carapibus | On total coloring of small fullerene nanodiscs* (Mariana Cruz, Celina Figueiredo, Diana Sasaki, Diane Castonguay) |
| 16:35 – 17:00 A | Carapibus | Cobertura de grafos aleatórios por caminhos multicoloridos (Antônio Fernandes, Guilherme Oliveira Mota, Tássio Naia) |
| 14:55 – 15:20 B | Tabatinga | The Hidden Subgroup Problem and Non-interactive Perfect Zero-Knowledge Proofs (Abner Costa, Henrique Hepp, Murilo da Silva, Leandro Zatesko) (Chair da sessão: Lehilton Pedrosa) |
| 15:20 – 15:45 B | Tabatinga | An Introduction to the Complexity Class of Pure Nash Equilibrium (Victor Hugo Wirz, Pedro Nuno Moura) |
| 15:45 – 16:10 B | Tabatinga | Complexidade e Estratégias Vencedoras de Jogos de Convexidade em Grafos (Raquel Folz Cavalcante, Rosiane de Freitas, Samuel Nascimento, Rudini Sampaio) |
| 16:10 – 16:35 B | Tabatinga | O Problema do Caminho Positivo Mínimo (Felipe Albuquerque Brito, Manoel Bezerra Campelo Neto, Tatiane Figueiredo) |
| 16:35 – 17:00 B | Tabatinga | Freeze-Tag Remains NP-hard on Binary and Ternary Trees (Lehilton Lelis Chaves Pedrosa, Lucas Silva) |
| 17:00 – 17:30 | COFFEE BREAK | |
| 17:30 – 18:30 | Tabatinga | Reunião da CEACO |
| TERÇA | Sala | |
| 09:00 – 09:15 | Carapibus | Premiação |
| 09:15 – 09:40 A | Carapibus | Coloração de identificação local em produto Cartesiano (Robson Oliveira, Márcia Cappelle, Hebert da Silva Coelho) (Chair da sessão: Márcia Capelle) |
| 09:40 – 10:05 A | Carapibus | Bounds on Identifying Codes in the Cartesian Product of a Path and a Star Graph (Juliana Félix, Márcia Cappelle) |
| 10:05 – 10:30 A | Carapibus | On (acyclic) proper orientations and the cartesian product (Júlio César Araújo, Alexandre Cezar) |
| 09:15 – 09:40 B | Areia Vermelha | Arredondamento de PL para o Problema de Localização de Instalações (Lehilton Lelis Chaves Pedrosa) (Chair da sessão: Teobaldo Leite Bulhões) |
| 09:40 – 10:05 B | Areia Vermelha | Eliminar Ciclos pela Remoção de um Emparelhamento Parametrizado pela Largura em Árvore é FPT (Carlos Vinícius Gomes Costa Lima, Thiago Marcilon, Cícero Samuel Morais) |
| 10:05 – 10:30 B | Areia Vermelha | Uma heurística híbrida para o problema de escalonamento de tarefas em uma máquina com tempos de setup dependentes da sequência e datas de liberação (Rafael Morais, Teobaldo Leite Bulhões Júnior, Anand Subramanian) |
| 10:30 – 11:00 | COFFEE BREAK | |
| 11:00 – 11:25 A | Carapibus | As árvores características dos grafos cordais comparabilidade não possuem grau limitado (Márcia Cerioli, Rodrigo Souto, Petrucio Viana) (Chair da sessão: Wanderson Lomenha) |
| 11:25 – 11:50 A | Carapibus | Número da sorte e grafos exoplanares livres de triângulos (Maycon Sambinelli, Fabio dos Santos de Souza) |
| 11:50 – 12:15 A | Carapibus | Coloração caminho não repetitiva de ladders circulares (João Pedro de Souza, Fábio Botler, Wanderson Lomenha) |
| 11:00 – 11:25 B | Areia Vermelha | Um Algoritmo Híbrido para o Problema de Roteamento de Veículos com Frota Heterogênea Robusto (Carlos Neves, Anand Subramanian, Pedro Munari) (Chair da sessão: Edna Hoshino) |
| 11:25 – 11:50 B | Areia Vermelha | Um algoritmo populacional para o problema de flow shop com bloqueio e minimização do makespan (Ewerton Teixeira, Anand Subramanian, Hugo Kramer) |
| 11:50 – 12:15 B | Areia Vermelha | Matheurísticas para o problema de roteamento de veículos com prêmios (Francisco Ferreira Lima Neto, Vagner Pedrotti, Edna Hoshino) |
| 12:30 – 14:00 | ALMOÇO | |
| 14:00-14:50 | Carapibus | Palestra do Cláudio L. Lucchesi: Aplicações de Grafos Pfaffianos (Chair: Vinícius dos Santos) |
| 14:55-15:20 A | Carapibus | Some results on irregular decomposition of graphs (Carla Lintzmayer, Guilherme Oliveira Mota, Lucas Rocha, Maycon Sambinelli) (Chair da sessão: João Pedro de Souza) |
| 15:20-15:45 A | Carapibus | Coloração total equilibrada dos snarks de Loupekine (Rieli Araújo, Diana Sasaki) |
| 15:45-16:10 A | Carapibus | On the conformable colorings of k-regular graphs (Mauro Nigro, Luerbio Faria, Diana Sasaki) |
| 16:10-16:35 A | Carapibus | Propriedades de fecho de linguagens (C, D)-Fuzzy (Valdigleis Costa, Antonio Farias, Benjamin Bedregal, Regivan Hugo Nunes Santiago) |
| 16:35-17:00 A | Carapibus | 5 Coloração Distância-2 em Fulerenes de Cintura 5 (Wanderson Lomenha, João Pedro de Souza, Diego Nicodemos) |
| 14:55-15:20 B | Areia Vermelha | Minimum Diameter Trees Subject to a Budget Constraint (Amanda Azevedo, Abilio Lucena) (Chair da sessão: Anand Subramanian) |
| 15:20-15:45 B | Areia Vermelha | Formulação matemática para o problema da árvore $t$-spanner de custo mínimo (Gabriel Sousa, Manoel Bezerra Campelo Neto) |
| 15:45-16:10 B | Areia Vermelha | Uma abordagem exata unificada para um conjunto de variantes do problema de roteamento de veículos com coleta e entrega simultâneas (Rafael Praxedes, Teobaldo Bulhões Júnior, Anand Subramanian, Eduardo Barboza) |
| 16:10-16:35 B | Areia Vermelha | Formulacões para o Problema da Compra Mínima (Sandro Uliana, Rafael Schouery) |
| 16:35-17:00 B | Areia Vermelha | Um Modelo de Otimização para um Problema Real de Programação de Horários de Trens Urbanos (Renata Mendes, Anand Subramanian, Bruno Bruck, Teobaldo Bulhões Júnior) |
Palestra do Anand Subramanian
Title: Hybrid iterated local search frameworks for classes of combinatorial optimization problems
Abstract: In this talk, we present two frameworks based on the iterated local search (ILS) metaheuristic for solving classes of combinatorial optimization problems. The first framework consists of a combination of ILS and the randomized variable neighborhood descent (RVND) procedure, whereas the second one is a matheuristic approach that integrates ILS, RVND and a mathematical programming-based procedure. We consider classes of problems that can be represented using a single sequence of elements (e.g., variants of the traveling salesman problem, single machine scheduling problems), multiple sequences of elements (e.g., vehicle routing problems, parallel machine scheduling problems), and multiple sets of elements (e.g., clustering problems). Moreover, we provide guidelines on how to efficiently perform move evaluation and feasibility checking during local search, as well as efficient mechanisms to improve computational performance.
Palestra do Cláudio L. Lucchesi
Título: Aplicações de Grafos Pfaffianos
Resumo: Esta palestra é primariamente de divulgação. Será apresentado um algoritmo polinomial para o reconhecimento de grafos bipartidos Pfaffianos, devido a McCuaig e, independentemente, a Robertson, Seymour e Thomas. Serão então abordadas algumas aplicações, particularmente na Teoria dos Grafos e na análise da estabilidade de compostos orgânicos.
Organizadores Gerais:
Cristina Gomes Fernandes (USP) – cris@ime.usp.br
Manoel Bezerra Campêlo Neto (UFC) – mcampelo@ufc.br
Vinicius Fernandes dos Santos (UFMG) – viniciussantos@dcc.ufmg.br
Apoio Local:
Teobaldo Leite Bulhões Júnior – tbulhoes@ci.ufpb.br
Organizadores do Comitê de Programa:
Cristina Gomes Fernandes (USP)
Manoel Bezerra Campêlo Neto (UFC)
Vinicius Fernandes dos Santos (UFMG)
Comitê de Programa (TPC):
Anand Subramanian, Universidade Federal da Paraíba
Álvaro Franco, Universidade Federal de Santa Catarina
Carlos Vinícius Gomes Costa Lima, Universidade Federal do Cariri
Cândida Silva, Universidade Federal de São Carlos, Campus Sorocaba
Críston Souza, Universidade Federal do Ceará
Cristiane Sato, Universidade Federal do ABC
Cristina Fernandes, Universidade de São Paulo
Diana Sasaki, Universidade do Estado do Rio de Janeiro
Edna Hoshino, Universidade Federal do Mato Grosso do Sul
Erika Coelho, Universidade Federal de Goiás
Fernanda Couto, Universidade Federal Rural do Rio de Janeiro
Gabriel Coutinho, Universidade Federal de Minas Gerais
Karolinna Maia, Universidade Federal do Ceará
Luís Cunha, Universidade Federal Fluminense
Manoel Bezerra Campelo Neto, Universidade Federal do Ceará
Marina Groshaus, Universidade Tecnológica Federal do Paraná
Márcia Cerioli, Universidade Federal do Rio de Janeiro
Rafael Melo, Universidade Federal da Bahia
Rafael Schouery, Universidade Estadual de Campinas
Ricardo Corrêa, Universidade Federal Rural do Rio de Janeiro
Rosiane de Freitas, Universidade Federal do Amazonas
Santiago Ravelo, Universidade Federal do Rio Grande do Sul
Tanilson Santos, Universidade Federal do Tocantins
Teobaldo Bulhões Júnior, Universidade Federal da Paraíba
Vinicius dos Santos, Universidade Federal de Minas Gerais
Contato para dúvidas:
