@PhdThesis{Lima2022,
   author       = {Alane Marie de Lima},
   title        = {Approximation Algorithm in Graphs via Sample Complexity },
   school       = {PPGInf/UFPR},
   year         = {2022},
   month        = {outubro},
   day          = {28},
   type         = {Doutorado},
   note         = {Orientador: Andre Luiz Vignatti e Murilo V. G. da Silva.  Banca: Eduardo Sany Laber (PUC-Rio),
                  Leandro Miranda Zatesko (UTFPR) e Guilherme Derenievicz (UFPR).},
   keywords     = {OrDScC,Universal2021},
   abstract     = {Grafos de grande porte advém de diversos contextos em fenômenos naturais e sociais. Contudo, algoritmos que escalam em complexidade de tempo cúbica e até mesmo quadrática, quando executados nesses grafos, podem ser computacionalmente custosos na prática. Neste trabalho, apresentamos esquemas de aproximação aleatorizados de tempo próximo de linear para dois problemas em grafos onde não se tem algoritmo conhecido de tempo estritamente subcúbico no número de vértices. Adicionalmente, para um terceiro problema, também apresentamos um esquema de aproximação aleatorizado de tempo próximo de linear, mas para o caso em que o grafo de entrada tem diâmetro logarítmico. Os algoritmos propostos foram projetados utilizando análise de complexidade de amostra, teoria de dimensão Vapnik–Chervonenkis e médias de Rademacher. Seja G = (V ,E) um grafo com n = |V| e m = |E|. O primeiro problema tratado neste trabalho é o de centralidade de percolação em um grafo G direcionado com pesos reais não-negativos. Tal medida quantifica a importância de um vértice em um grafo que está passando por um processo de contágio. Neste trabalho, apresentamos um algorimo de aproximação de tempo O(mlog nlog diamV (G)) para estimar a centralidade de percolação de cada vértice de V, onde diamV (G) é número máximo de vértices em um caminho mínimo em G. O segundo problema é uma versão relaxada do problema de computar todos os caminhos mínimos entre todos os pares de vértices (APSP). Nesta versão, iremos computar todos os caminhos de G que tenham "centralidade" pelo menos e, para 0 < epsilon < 1 constante, medida esta que está relacionada a uma generalização da centralidade de intermediação. O algoritmo proposto executa em tempo O(m log n + (diamV (G))2). O terceiro problema é o de coeficiente de agrupamento local de cada vértice de um grafo G. Neste trabalho propomos um algoritmo para este problema que roda em tempo O(delta lg delta +m), onde delta é o grau máximo de um vértice de um grafo. Finalmente, neste trabalho também apresentamos algoritmos de aproximação para os problemas do conjunto dominante mínimo (MDS) e da cobertura por vértices mínima (MVC). Em ambos aplicamos técnicas probabilísticas, contudo não utilizamos análise de complexidade de amostra nestes casos. Para estes problemas, obtivemos limitantes mais justos lidando com o problema diretamente em um modelo específico de grafo aleatório lei de potência. Em particular, mostramos que o fator de aproximação esperado para o problema MDS é assintoticamente no máximo 9.14, e para o problema MVC, o fator é assintoticamente menor do que 2. Tais valores superam os limitantes conhecidos da literatura.},
   __url        = {},
   __url_pdf    = {}
}

{"_id":"pereSmmLj4hhBciNk","bibbaseid":"delima-approximationalgorithmingraphsviasamplecomplexity-2022","author_short":["de Lima, A. M."],"bibdata":{"bibtype":"phdthesis","type":"Doutorado","author":[{"firstnames":["Alane","Marie"],"propositions":["de"],"lastnames":["Lima"],"suffixes":[]}],"title":"Approximation Algorithm in Graphs via Sample Complexity ","school":"PPGInf/UFPR","year":"2022","month":"outubro","day":"28","note":"Orientador: Andre Luiz Vignatti e Murilo V. G. da Silva. Banca: Eduardo Sany Laber (PUC-Rio), Leandro Miranda Zatesko (UTFPR) e Guilherme Derenievicz (UFPR).","keywords":"OrDScC,Universal2021","abstract":"Grafos de grande porte advém de diversos contextos em fenômenos naturais e sociais. Contudo, algoritmos que escalam em complexidade de tempo cúbica e até mesmo quadrática, quando executados nesses grafos, podem ser computacionalmente custosos na prática. Neste trabalho, apresentamos esquemas de aproximação aleatorizados de tempo próximo de linear para dois problemas em grafos onde não se tem algoritmo conhecido de tempo estritamente subcúbico no número de vértices. Adicionalmente, para um terceiro problema, também apresentamos um esquema de aproximação aleatorizado de tempo próximo de linear, mas para o caso em que o grafo de entrada tem diâmetro logarítmico. Os algoritmos propostos foram projetados utilizando análise de complexidade de amostra, teoria de dimensão Vapnik–Chervonenkis e médias de Rademacher. Seja G = (V ,E) um grafo com n = |V| e m = |E|. O primeiro problema tratado neste trabalho é o de centralidade de percolação em um grafo G direcionado com pesos reais não-negativos. Tal medida quantifica a importância de um vértice em um grafo que está passando por um processo de contágio. Neste trabalho, apresentamos um algorimo de aproximação de tempo O(mlog nlog diamV (G)) para estimar a centralidade de percolação de cada vértice de V, onde diamV (G) é número máximo de vértices em um caminho mínimo em G. O segundo problema é uma versão relaxada do problema de computar todos os caminhos mínimos entre todos os pares de vértices (APSP). Nesta versão, iremos computar todos os caminhos de G que tenham \"centralidade\" pelo menos e, para 0 < epsilon < 1 constante, medida esta que está relacionada a uma generalização da centralidade de intermediação. O algoritmo proposto executa em tempo O(m log n + (diamV (G))2). O terceiro problema é o de coeficiente de agrupamento local de cada vértice de um grafo G. Neste trabalho propomos um algoritmo para este problema que roda em tempo O(delta lg delta +m), onde delta é o grau máximo de um vértice de um grafo. Finalmente, neste trabalho também apresentamos algoritmos de aproximação para os problemas do conjunto dominante mínimo (MDS) e da cobertura por vértices mínima (MVC). Em ambos aplicamos técnicas probabilísticas, contudo não utilizamos análise de complexidade de amostra nestes casos. Para estes problemas, obtivemos limitantes mais justos lidando com o problema diretamente em um modelo específico de grafo aleatório lei de potência. Em particular, mostramos que o fator de aproximação esperado para o problema MDS é assintoticamente no máximo 9.14, e para o problema MVC, o fator é assintoticamente menor do que 2. Tais valores superam os limitantes conhecidos da literatura.","__url":"","__url_pdf":"","bibtex":"@PhdThesis{Lima2022,\n author = {Alane Marie de Lima},\n title = {Approximation Algorithm in Graphs via Sample Complexity },\n school = {PPGInf/UFPR},\n year = {2022},\n month = {outubro},\n day = {28},\n type = {Doutorado},\n note = {Orientador: Andre Luiz Vignatti e Murilo V. G. da Silva. Banca: Eduardo Sany Laber (PUC-Rio),\n Leandro Miranda Zatesko (UTFPR) e Guilherme Derenievicz (UFPR).},\n keywords = {OrDScC,Universal2021},\n abstract = {Grafos de grande porte advém de diversos contextos em fenômenos naturais e sociais. Contudo, algoritmos que escalam em complexidade de tempo cúbica e até mesmo quadrática, quando executados nesses grafos, podem ser computacionalmente custosos na prática. Neste trabalho, apresentamos esquemas de aproximação aleatorizados de tempo próximo de linear para dois problemas em grafos onde não se tem algoritmo conhecido de tempo estritamente subcúbico no número de vértices. Adicionalmente, para um terceiro problema, também apresentamos um esquema de aproximação aleatorizado de tempo próximo de linear, mas para o caso em que o grafo de entrada tem diâmetro logarítmico. Os algoritmos propostos foram projetados utilizando análise de complexidade de amostra, teoria de dimensão Vapnik–Chervonenkis e médias de Rademacher. Seja G = (V ,E) um grafo com n = |V| e m = |E|. O primeiro problema tratado neste trabalho é o de centralidade de percolação em um grafo G direcionado com pesos reais não-negativos. Tal medida quantifica a importância de um vértice em um grafo que está passando por um processo de contágio. Neste trabalho, apresentamos um algorimo de aproximação de tempo O(mlog nlog diamV (G)) para estimar a centralidade de percolação de cada vértice de V, onde diamV (G) é número máximo de vértices em um caminho mínimo em G. O segundo problema é uma versão relaxada do problema de computar todos os caminhos mínimos entre todos os pares de vértices (APSP). Nesta versão, iremos computar todos os caminhos de G que tenham \"centralidade\" pelo menos e, para 0 < epsilon < 1 constante, medida esta que está relacionada a uma generalização da centralidade de intermediação. O algoritmo proposto executa em tempo O(m log n + (diamV (G))2). O terceiro problema é o de coeficiente de agrupamento local de cada vértice de um grafo G. Neste trabalho propomos um algoritmo para este problema que roda em tempo O(delta lg delta +m), onde delta é o grau máximo de um vértice de um grafo. Finalmente, neste trabalho também apresentamos algoritmos de aproximação para os problemas do conjunto dominante mínimo (MDS) e da cobertura por vértices mínima (MVC). Em ambos aplicamos técnicas probabilísticas, contudo não utilizamos análise de complexidade de amostra nestes casos. Para estes problemas, obtivemos limitantes mais justos lidando com o problema diretamente em um modelo específico de grafo aleatório lei de potência. Em particular, mostramos que o fator de aproximação esperado para o problema MDS é assintoticamente no máximo 9.14, e para o problema MVC, o fator é assintoticamente menor do que 2. Tais valores superam os limitantes conhecidos da literatura.},\n __url = {},\n __url_pdf = {}\n}\n\n","author_short":["de Lima, A. M."],"key":"Lima2022","id":"Lima2022","bibbaseid":"delima-approximationalgorithmingraphsviasamplecomplexity-2022","role":"author","urls":{},"keyword":["OrDScC","Universal2021"],"metadata":{"authorlinks":{}}},"bibtype":"phdthesis","biburl":"http://www.inf.ufpr.br/teoria/universal2021/orientacoes.bib","dataSources":["A5KFFBhQF4wDQsTFG"],"keywords":["ordscc","universal2021"],"search_terms":["approximation","algorithm","graphs","via","sample","complexity","de lima"],"title":"Approximation Algorithm in Graphs via Sample Complexity ","year":2022}