On rounding algorithms for the 2-edge-connected spanning subgraph problem (2024)
- Authors:
- Autor USP: AZEVEDO, GABRIEL MORETE DE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2024.tde-22012025-113608
- Subjects: ALGORITMOS DE APROXIMAÇÃO; TEORIA DOS GRAFOS
- Keywords: 2-edge-connected spanning subgraph; Approximation algorithms; Aumento de conexidade em emparelhamentos; Conexidade de grafos; Gap de integralidade; Graph connectivity; Integrality ratio; Matching augmentation; Subgrafo 2-aresta-conexo
- Agências de fomento:
- Language: Inglês
- Abstract: Um grafo conexo sem laços é 2-aresta-conexo se, após a remoção de qualquer uma de suas arestas, o grafo que se obtém é conexo. Diversos problemas em otimização combinatória consistem em, dado um grafo com custos nas arestas, encontrar um subgrafo gerador de menor custo que satisfaz certas restrições de conexidade. O problema do subgrafo 2-aresta-conexo mínimo (2-ECSSP, sigla em inglês) é um problema desse tipo. Ele pode ser formulado como um problema de otimização linear inteira, cujo objetivo é selecionar arestas de menor custo total que satisfazem a restrição de que todo corte do grafo dado é coberto por ao menos duas das arestas selecionadas. Trata-se de um problema NP-difícil. Essa dissertação discute algoritmos para três variantes do 2-ECSSP, que encontram soluções inteiras arredondando soluções meio-inteiras da correspondente relaxação linear. Essa família de soluções geralmente induz o maior gap de integralidade para diversas variantes do 2-ECSSP. Primeiramente, investigamos o 2-ECSSP meio-inteiro com custos irrestritos. Desenvolvemos um 5/3-arredondamento inédito no qual acreditamos ser o primeiro com um fator melhor que 2. Além disso, desenvolvemos uma redução que nos permite restringir a entrada a grafos 4-aresta-conexos com grau no máximo 5. Em seguida, estudamos o problema de aumento de conexidade de emparelhamentos (um subproblema do 2-ECSSP) no qual os custos das arestas são 0 ou 1 e as arestas de custo zero definem um emparelhamento. Discutimos umamelhor-que-2-approximação proposta em 2022 por Bamas, Drygala e Svensson, apresentamos uma prova completa do resultado e determinamos um fator de aproximação aprimorado. Além disso, respondemos conjecturas propostas e apresentamos experimentos computacionais para embasar nossas descobertas. Por fim, discutimos o problema do multisubgrafo 2-aresta-conexo mínimo (2-ECSMP), uma variante do 2-ECSSP na qual é permitido selecionar múltiplas cópias da mesma aresta. Discutimos um resultado de Boyd et al. publicado em 2022, que propõe um 4/3-arredondamento para o 2-ECSMP meio-inteiro. Utilizando as técnicas propostas pelos autores, desenvolvemos resultados inéditos sobre decomposição de grafos 4-regulares 4-aresta-conexos. Por fim, propomos duas conjecturas sobre os resultados de decomposição, sugerindo caminhos para novas pesquisas
- Imprenta:
- Data da defesa: 11.07.2024
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
AZEVEDO, Gabriel Morete de. On rounding algorithms for the 2-edge-connected spanning subgraph problem. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/. Acesso em: 05 ago. 2025. -
APA
Azevedo, G. M. de. (2024). On rounding algorithms for the 2-edge-connected spanning subgraph problem (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/ -
NLM
Azevedo GM de. On rounding algorithms for the 2-edge-connected spanning subgraph problem [Internet]. 2024 ;[citado 2025 ago. 05 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/ -
Vancouver
Azevedo GM de. On rounding algorithms for the 2-edge-connected spanning subgraph problem [Internet]. 2024 ;[citado 2025 ago. 05 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/
Informações sobre o DOI: 10.11606/D.45.2024.tde-22012025-113608 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
