Search

El tratamiento térmico de endurecimiento superficial por láser aporta calor en un área específica, lo cual permite que el interior de la pieza se mantenga frío y propicie la conducción de calor hacia el interior de la pieza, se alcanzan velocidades de enfriamiento muy elevadas, dejando a un lado la necesidad de utilizar un medio de temple o líquidos refrigerantes. En piezas cilíndricas de gran longitud es necesario realizar pasos múltiples del spot láser para cubrir una determinada área de trabajo, este proceso de avance genera trayectorias traslapadas que forman una capa endurecida no uniforme, analizando este principio y los factores que intervienen en el proceso de temple, se desarrolló una estrategia que emplea conceptos de propiedades de los aceros al carbono, diagramas de temperatura, tiempo y transformación, curvas de enfriamiento continuo, para comprender el fenómeno de temple, y aportar los datos de entrada necesarios al software, obteniendo como resultado cada uno de los casos de un diseño de experimentos previamente determinado, los valores óptimos de este estudio se muestran en el análisis del diseño de experimentos, y se genera un aporte especial para determinar el grado de uniformidad de la capa de martensita resultando el diagrama ternario de factores.

El presente trabajo tiene como objetivo principal aplicar una metodología de enseñanza muy utilizada a nivel de educación media y superior para el desarrollo de habilidades complementarias y por supuesto el aprendizaje de los principios de la dinámica rotacional, para ello se aplica la metodología de enseñanza basada en proyectos, es así que se construyó un prototipo para experimentar con masas y cuerpos geométricos que al aplicar las ecuaciones y cálculos respectivos se encuentra los momentos de inercia, estos valores se validan determinando el error respecto a los valores estimados teóricamente. Luego se mide mediante una encuesta el impacto sobre los estudiantes, resultando positivo en la construcción de conocimientos y se pudo identificar además el desarrollo de competencias en comunicación de estudiantes con el docente, aplicación de la ciencia a problemas reales y trabajo en equipo. Finalmente se concluye que es una herramienta muy recomendada en la educación superior para la enseñanza de la física y se podría aplicar a asignaturas de similares características.

In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound. In this paper, we introduce the [Formula: see text]-Packing with [Formula: see text]-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let [Formula: see text] be all possible subsets of vertices of [Formula: see text] each of size at most [Formula: see text], and [Formula: see text] be a function. The [Formula: see text]-Packing with [Formula: see text]-Overlap problem seeks at least [Formula: see text] induced subgraphs in a graph [Formula: see text] subject to: (i) each subgraph has at most [Formula: see text] vertices and obeys a property [Formula: see text], and (ii) for any pair [Formula: see text], with [Formula: see text], [Formula: see text] (i.e., the pair [Formula: see text] does not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets [Formula: see text], and no pair of subgraphs may share vertices from the sets of [Formula: see text]. In addition, we propose similar formulations for packing hypergraphs. We give an [Formula: see text] algorithm for our problems where [Formula: see text] is the parameter and [Formula: see text] and [Formula: see text] are constants, provided that: (i) [Formula: see text] is computable in polynomial time in [Formula: see text] and (ii) the function [Formula: see text] satisfies specific conditions. Specifically, [Formula: see text] is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in [Formula: see text] and [Formula: see text]. Motivated by practical applications we give several examples of [Formula: see text] functions which meet those conditions.

The $k$-atomicity property can be used to describe the consistency of data operations in large distributed storage systems. The weak consistency guarantees offered by such systems are seen as a nec...

We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exists a set of points and a set of unit disks in the plane, and the points and disk centres are conned to a strip of xed height. An optimal solution to the WSDUDC problem is a set of disks of minimum cardinality that covers all points in the input set. We describe a range of approximation algorithms for the problem, including 4- and 3-approximate algorithms which apply for strips of height 2 p 2=3 0:94 and 0:8 units respectively, as well as a general scheme for any strip with less than unit height. We prove that the WSDUDC problem is NP-complete on strips of any xed height, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of xed height. Finally, we discuss how these results may be applied to known DUDC approximation algorithms.

We introduce a new representation of the inverted index that performs faster ranked unions and intersections while using similar space. Our index is based on the treap data structure, which allows us to intersect/merge the document identifiers while simultaneously thresholding by frequency, instead of the costlier two-step classical processing methods. To achieve compression, we represent the treap topology using different alternative compact data structures. Further, the treap invariants allow us to elegantly encode differentially both document identifiers and frequencies. We also show how to extend this representation to support incremental updates over the index. Results show that, under the tf-idf scoring scheme, our index uses about the same space as state-of-the-art compact representations, while performing up to 2--20 times faster on ranked single-word, union, or intersection queries. Under the BM25 scoring scheme, our index may use up to 40% more space than the others and outperforms them less frequently but still reaches improvement factors of 2--20 in the best cases. The index supporting incremental updates poses an overhead of 50%--100% over the static variants in terms of space, construction, and query time.

We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no worse than an algorithm B if there is a bijection $$\pi $$ defined over all request sequences of a given size such that the cost of A on $$\sigma $$ is no more than the cost of B on $$B(\pi (\sigma ))$$ . We also study a relaxation of bijective analysis, termed average analysis, in which we compare two algorithms based on their corresponding average costs over request sequences of a given size. We apply these new techniques in the context of two fundamental online problems, namely paging and list update. For paging, we show that any two lazy online algorithms are equivalent under bijective analysis. This result demonstrates that, without further assumptions on characteristics of request sequences, it is unlikely, or even undesirable, to separate online paging algorithms based on their performance. However, once we restrict the set of request sequences to those exhibiting locality of reference, and in particular using a model of locality due to Albers et al. (J Comput Syst Sci 70(2):145–175, 2005), we demonstrate that Least-Recently-Used (LRU) is the unique optimal strategy according to average analysis. This is, to our knowledge, the first deterministic model to provide full theoretical backing to the empirical observation that LRU is preferable in practice. Concerning list update, we obtain similar conclusions, in terms of the bijective comparison of any two online algorithms, and in terms of the superiority (albeit not necessarily unique) of the Move-To-Front (MTF) heuristic in the presence of locality of reference.

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce ź(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth ź, there is an online algorithm that receives O (n(log ź + log log N))* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ź 3. Through another lower bound argument, we show that at least n2(logźź1.22)$\frac {n}{2}(\log \alpha - 1.22)$ bits of advice is required to obtain an optimal solution for metric spaces of treewidth ź, where 4 ≤ ź < 2k.

We consider the problem of discovering overlapping communities in networks that we model as generalizations of the Set and Graph Packing problems with overlap. As usual for Set Packing problems, we seek a collection S ′ ⊆ S consisting of at least k sets subject to certain disjointness restrictions. In the r -Set Packing with t -Membership, each element of U belongs to at most t sets of S ′ , while in r -Set Packing with t -Overlap, each pair of sets in S ′ overlaps in at most t elements. For both problems, each set of S has at most r elements. Similarly, both of our Graph Packing problems seek a collection K of at least k subgraphs in a graph G , each isomorphic to a graph H ∈ H . In H -Packing with t -Membership, each vertex of G belongs to at most t subgraphs of K , while in H -Packing with t -Overlap, each pair of subgraphs in K overlaps in at most t vertices. For both problems, each member of H has at most r vertices and m edges, where t , r , and m are constants. Here, we show NP-completeness results for all of our packing problems. Furthermore, we give a dichotomy result for the H -Packing with t -Membership problem analogous to the Kirkpatrick and Hell dichotomy [Kirkpatrick and Hell 1978]. Using polynomial parameter transformations, we reduce the r -Set Packing with t -Membership to a problem kernel with O (( r + 1) r k r ) elements and the H -Packing with t -Membership and its edge version to problem kernels with O (( r + 1) r k r ) and O (( m + 1) m k m ) vertices, respectively. On the other hand, by generalizing [Fellows et al. 2008; Moser 2009], we achieve a kernel with O ( r r k r − t − 1 ) elements for the r -Set Packing with t -Overlap and kernels with O ( r r k r − t − 1 ) and O ( m m k m − t − 1 ) vertices for the H -Packing with t -Overlap and its edge version, respectively. In all cases, k is the input parameter, while t , r , and m are constants.

We consider the problem of managing a bounded size First-In-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when a policy is permitted to drop already admitted packets) and non-push-out cases. We provide worst-case guarantees for the throughput performance of our algorithms, proving both lower and upper bounds on their competitive ratio against the optimal algorithm, and conduct a comprehensive simulation study that experimentally validates predicted theoretical behavior.

Modern network processors increasingly deal with packets that require heterogeneous processing. We consider the problem of managing a bounded size input queue buffer where each packet requires several rounds of processing before it can be transmitted out. This to maximize the total number of successfully transmitted packets. Usually the transmission order of the packets is induced by the processing order. However, processing order can have a significant impact on the performance of buffer management policies even if the order of transmission is fixed. For this reason we decouple processing order from transmission order and restrict our transmission order to First-In-First-Out (FIFO) but allow for different orders of packet processing, introducing the class of such policies as Semi-FIFO. In this work, we build a taxonomy of Semi-FIFO policies and provide worst case guarantees for different processing orders. We consider various special cases and properties of Semi-FIFO policies, e.g., greedy, work-conserving, lazy, and push-out policies, and show how these properties affect performance. We generalize our results to additional constraints on the push-out mechanism designed to deal with copying cost. Further, we conduct a comprehensive simulation study that validates our results. pub

We study optimization problems for the Euclidean Minimum Spanning Tree (MST) problem on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the Minimum Spanning Tree with Neighborhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the max-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.

We introduce the k-H-Packing with t-Overlap problem to formalize the problem of discovering overlapping communities in real networks. More precisely, in the k-H-Packing with t-Overlap problem, we search in a graph G for at least k subgraphs each isomorphic to a graph H such that any pair of subgraphs shares at most t vertices. In contrast with previous work where communities are disjoint, we regulate the overlap through a variable t. Our focus is on the parameterized complexity of the k-H-Packing with t-Overlap problem. Here, we provide a new technique for this problem generalizing the crown decomposition technique [2]. Using our global rule, we achieve a kernel with size bounded by 2(rk r) for the k-Kr-Packing with (r 2)Overlap problem. That is, when H is a clique of size r and t = r 2. In addition, we introduce the first parameterized algorithm for the kH-Packing with t-Overlap problem when H is an arbitrary graph of size r. Our algorithm combines a bounded search tree with a greedy localization technique and runs in time O(r rk k (r t 1)k+2 n r ), where n = |V (G)|, r = |V (H)|, and t < r. Finally, we apply this search tree algorithm to the kernel obtained for the k-Kr-Packing with (r 2)-Overlap problem, and we show that this approach is faster than applying a brute-force algorithm in the kernel. In all our results, r and t are constants.

It is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning’s working set model and express the performance of well known algorithms in terms of this parameter. This explicitly introduces parameterized-style analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning’s working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their experimentally observed relative strengths. It also reflects the intuition that a larger cache leads to a better performance. We also apply the parameterized analysis framework to list update and show that certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.

We give lower bounds for various natural node- and edge-based local strategies for exploring a graph. We consider this problem both in the setting of an arbitrary graph as well as the abstraction of a geometric exploration of a space by a robot, both of which have been extensively studied. We consider local exploration policies that use time-of-last- visit or alternatively least-frequently-visited local greedy strategies to select the next step in the exploration path. Both of these strategies were previously considered by Cooper et al. (2011) for a scenario in which counters for the last visit or visit frequency are attached to the edges. In this work we consider the case in which the counters are associated with the nodes, which for the case of dual graphs of geometric spaces could be argued to be intuitively more natural and likely more efficient. Surprisingly, these alternate strategies give worst-case superpolynomial/ exponential time for exploration, whereas the least-frequently visited strategy for edges has a polynomially bounded exploration time, as shown by Cooper et al. (2011)., arXiv admin note: text overlap with arXiv:1410.2295

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time. In contrast, interruptible algorithms may be interrupted throughout their execution, at which point they must report their current solution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the classical case, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper we study the more general setting of scheduling contract algorithms at the presence of soft deadlines. This is motivated by the observation of practitioners that soft deadlines are as common an occurrence as hard deadlines, if not more common. In our setting, at the time t of interruption the algorithm is given an additional window of time w(t) ≤ c ċ t to continue the contract or, indeed, start a new contract (for some fixed constant c). We explore this variation using the acceleration ratio, which is the canonical measure of performance for these schedules, and derive schedules of optimal acceleration ratio for all functions w.

In this paper, we investigate the problem of graph list colouring in the on-line setting. We provide several results on paintability of graphs in the model introduced by Schauz [18] and Zhu [25]. We prove that the on-line version of Ohba’s conjecture is true for the class of planar graphs. We show that the conjecture for partial list colouring on-line holds for several graph classes, namely claw-free graphs, maximal planar graphs, series-parallel graphs, and chordal graphs.

We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, each packet requires several rounds of processing before it can be transmitted out, and the goal is to maximize the throughput, i.e., total size of successfully transmitted packets. Our work addresses the tension between two conflicting algorithmic approaches: favoring packets with fewer processing requirements as opposed to packets of larger size. We present a novel model for studying such systems and study the performance of online algorithms that aim to maximize throughput. pub

We give lower bounds for various natural node- and edge-based local strategies for exploring a graph. We consider this problem both in the setting of an arbitrary graph as well as the abstraction of a geometric exploration of a space by a robot, both of which have been extensively studied. We consider local exploration policies that use time-of-last-visit or alternatively least-frequently-visited local greedy strategies to select the next step in the exploration path. Both of these strategies were previously considered by Cooper et al. (2011) for a scenario in which counters for the last visit or visit frequency are attached to the edges. In this work we consider the case in which the counters are associated with the nodes, which for the case of dual graphs of geometric spaces could be argued to be intuitively more natural and likely more efficient. Surprisingly, these alternate strategies give worst-case superpolynomial/exponential time for exploration, whereas the least-frequently-visited strategy for edges has a polynomially bounded exploration time, as shown by Cooper et al. (2011).

We consider the problem of multiple agents or robots searching in a coordinated fashion for a target in the plane. This is motivated by Search and Rescue operations (SAR) in the high seas which in the past were often performed with several vessels, and more recently by swarms of aerial drones and/or unmanned surface vessels. Coordinating such a search in an effective manner is a non trivial task. In this paper, we develop first an optimal strategy for searching with k robots starting from a common origin and moving at unit speed. We then apply the results from this model to more realistic scenarios such as differential search speeds, late arrival times to the search effort and low probability of detection under poor visibility conditions. We show that, surprisingly, the theoretical idealized model still governs the search with certain suitable minor adaptations.

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.

We give an explicit representation for the offline optimum strategy for list update under the MRM model of Martinez and Roura [C. Martinez, S. Roura, On the competitiveness of the move-to-front rule, Theoret. Comput. Sci. 242 (1-2) (2000) 3130-325] and Munro [J.I. Munro, On the competitiveness of linear search, in: Proc. 8th Annual European Symposium on Algorithms (ESA 2000), in: Lecture Notes in Comput. Sci., vol. 1879, 2000, pp. 338-345] and give an O(n^3) algorithm to compute it. This is in contrast to the standard model of Sleator and Tarjan [D.D. Sleator, R.E. Tarjan, Amortized efficiency of list update and paging rules, Commun. ACM 28 (2) (1985) 202-208] under which computing the offline optimum was shown to be NP-hard [C. Ambuhl, Offline list update is NP-hard, in: Proc. 8th Annual European Symposium on Algorithms (ESA 2000), in: Lecture Notes in Comput. Sci., vol. 1879, 2000, pp. 42-51]. This algorithm follows from a new characterization theorem for realizable visiting sequences in the MRM model.