Source author record

Lehilton L. C. Pedrosa

Lehilton L. C. Pedrosa appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics

Catalog footprint

What is connected

5works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

A parameterized approximation algorithm for the Multiple Allocation $k$-Hub Center

In the Multiple Allocation $k$-Hub Center (MA$k$HC), we are given a connected edge-weighted graph $G$, sets of clients $\mathcal{C}$ and hub locations $\mathcal{H}$, where ${V(G) = \mathcal{C} \cup \mathcal{H}}$, a set of demands $\mathcal{D} \subseteq \mathcal{C}^2$ and a positive integer $k$. A solution is a set of hubs $H \subseteq \mathcal{H}$ of size $k$ such that every demand $(a,b)$ is satisfied by a path starting in $a$, going through some vertex of $H$, and ending in $b$. The objective is to minimize the largest length of a path. We show that finding a $(3-ε)$-approximation is NP-hard already for planar graphs. For arbitrary graphs, the approximation lower bound holds even if we parameterize by $k$ and the value $r$ of an optimal solution. An exact FPT algorithm is also unlikely when the parameter combines $k$ and various graph widths, including pathwidth. To confront these hardness barriers, we give a $(2+ε)$-approximation algorithm parameterized by treewidth, and, as a byproduct, for unweighted planar graphs, we give a $(2+ε)$-approximation algorithm parameterized by $k$ and $r$. Compared to classical location problems, computing the length of a path depends on non-local decisions. This turns standard dynamic programming algorithms impractical, thus our algorithm approximates this length using only local information. We hope these ideas find application in other problems with similar cost structure.

preprint2020arXiv

Computing the Largest Bond and the Maximum Connected Cut of a Graph

The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$. Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.

preprint2016arXiv

Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center

In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated α-fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if α centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the {0,L}-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the previously best known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming α is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault- tolerant k-supplier problem.

preprint2014arXiv

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+γ$, for some arbitrarily small number $γ> 0$. Our algorithm is polynomial on $\log 1/γ$, and thus $γ$ is part of the problem input. For the special case that $γ$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+γ$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the $L_p$-norm.

preprint2013arXiv

A Systematic Approach to Bound Factor-Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems

A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the Metric Facility Location Problem (MFLP) and to a generalization where the distance function is a squared metric. We call this generalization the Squared Metric Facility Location Problem (SMFLP) and prove that there is no approximation factor better than 2.04, assuming P $\neq$ NP. Then, we analyze the best known algorithms for the MFLP based on primal-dual and LP-rounding techniques when they are applied to the SMFLP. We prove very tight bounds for these algorithms, and show that the LP-rounding algorithm achieves a ratio of 2.04, and therefore has the best factor for the SMFLP. We use UPFRPs in the dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, improving some of the previous analysis for the MFLP.