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
- Status:
- Artigo possui versão em acesso aberto em repositório (Green Open Access)
- Versão do Documento:
- Versão submetida (Pré-print)
- Acessar versão aberta:
-
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://teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/. Acesso em: 10 abr. 2026. -
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://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 2026 abr. 10 ] Available from: https://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 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-22012025-113608/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
