949 research outputs found
Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
No full textWe consider the problem of computing a Steiner tree of minimum cost under a k-hop constraint which requires the depth of the tree to be at most k. Our main result is an exact algorithm for metrics induced by graphs of bounded treewidth that runs in time n^O(k). For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if k is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the k-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension
SUPERSET: A (Super)Natural Variant of the Card Game SET
No full textWe consider Superset, a lesser-known yet interesting variant of the famous card game Set. Here, players look for Supersets instead of Sets, that is, the symmetric difference of two Sets that intersect in exactly one card. In this paper, we pose questions that have been previously posed for Set and provide answers to them; we also show relations between Set and Superset.
For the regular Set deck, which can be identified with F^3_4, we give a proof for the fact that the maximum number of cards that can be on the table without having a Superset is 9. This solves an open question posed by McMahon et al. in 2016. For the deck corresponding to F^3_d, we show that this number is Omega(1.442^d) and O(1.733^d). We also compute probabilities of the presence of a superset in a collection of cards drawn uniformly at random. Finally, we consider the computational complexity of deciding whether a multi-value version of Set or Superset is contained in a given set of cards, and show an FPT-reduction from the problem for Set to that for Superset, implying W[1]-hardness of the problem for Superset
A QPTAS for the General Scheduling Problem with Identical Release Dates
No full textThe General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems.
We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval
The symbols in the poetry of ruben dario
No full text碩士本論文主要分為三個章節，第一章，何為象徵符號？本章節主要藉由象徵理論學家，威爾伯 (Wilbur Marshall Urban)、弗萊(Northrop Frye)、托多羅夫(Tzvetan Todorov)、賽洛特(Juan-Eduardo Cirlot)以及其他學者的相關文獻解釋象徵符號的定義以及象徵符號在文學作品中的定義。
第二章針對達里歐的生平、作品以及達里歐在現實主義時期的重要性為論述重點。筆者根據達里歐的生平以及生長年代來了解他的作品特色，達里歐一生多采多姿，尤其感情方面更為豐富，這些人生際遇皆影響達里歐的寫作風格。達里歐不只是詩人，也是歷史的見證者，從他的作品中可以看到政治歷史的變化趨勢。達里歐著作極為豐富，筆者在本章節挑選三本可以代表達里歐的作品：《藍》(Azul)、《每日詩》(Prosas profanes)以及《生命與希望之歌》(Cantos de vida y esperanza)。達里歐與現實主義有著密不可分的關係，他的寫作風格不僅受到現實主義作家的影響，同時也是影響現實主義作家的重要人士之一。
第三章筆者不僅針對達里歐的詩集作品分析，同時也分析其散文作品，如《稀奇》(Los raros)。筆者將經常出現於達里歐作品中的象徵符號分為三個部分：顏色符號、禽鳥符號和寶石符號。顏色符號部分主要分析的顏色為藍色、綠色、白色以及黑色。禽鳥符號則針對天鵝、鴿子、孔雀和老鷹。而最後的寶石符號則以珠寶、寶石、鑽石、琥珀、黃金和水晶為主要分析內容。
最後筆者希望藉由這篇論文的研究，能讓大家了解象徵符號經由作家的詮釋，即使相同的符號，也擁有不同的意義。此外也希望大家能透過此篇論文認識文學史上重要的拉丁美洲作家盧本達里歐先生。In this thesis we explore definitions of symbols and the life of the author in the book of Ruben Dario. Dario is an author who emphasized the importance of the use of symbols though out his books. Therefore we might consider him as a master specialized in writing with symbols.
We divide the thesis into three chapters. In the first chapter, we give details to the definition of the symbols. According to scholars like Urban, Frye, Todorov and Cirlot, we are able to understand symbols in forms of signs, images and words. The concept of the symbols is relatively comprehensive, taking into consideration that a symbol is not always a sign; in fact, it is much more than a sign.
In the second chapter, we describe Ruben Dario about his life, literary works and the times when he lived. His life was interesting, colorful and varied. He was not only a poet but a public figure, having been an ambassador of Nicaragua in Spain. Dario wrote many pieces and each was important to him. Based on his narration, there are three books that can represent Ruben Dario, Azul, Prosas profanas and Cantos de vida y esperanza.
Dario was the master of Modernism, mainly because of the great influence of Latin America. Not only did Ruben Dario influence the poets of Modernism but was influenced by other poets in the same period.
In the last chapter we examine the symbols in the poetry of Dario and we divided the symbols into three parts: the colors, birds and precious stones. The first part, we examine the colors. There are blue, green, and black. In the second part, we deal with the symbols of birds, including swans, pigeons, peacocks and eagles. And in the last part, we talk about precious stones. We analyze the symbols of agate, ruby, diamond, crystal and gold. Finally, we end up with the conclusions and bibliography.INTRODUCCION 1
Motivo y objetivo 1
Metodologia de trabajo 3
CAPITULO I: ¿QUE SON LOS SIMBOLOS? 5
1.1 Teorias del simbolo 6
1.2 Los simbolos en la literatura 15
CAPITULO II: RUBEN DARIO Y SU OBRA POETICA 22
2.1 Vida 22
2.2 Obra literaria 28
2.3 Ruben Dario y el Modernismo 35
CAPITULO III: LOS SIMBOLOS EN LA POESIA DE RUBEN DARIO 40
3.1 Colores 40
3.2 Aves 45
3.3 Piedras preciosas 59
CONCLUSION 72
BIBLIOGRAFIA 77
ANEXOS 83學號: 698120028, 學年度: 10
Scheduling Self-Suspending Tasks: New and Old Results
No full textIn computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community.
This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art
Scheduling Self-Suspending Tasks: New and Old Results (Artifact)
No full textIn computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community.
This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art
On the Complexity of Anchored Rectangle Packing
No full textIn the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard.
In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation
Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types
No full textWe study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria
A better lower bound for Lower-Left Anchored Rectangle Packing
No full textGiven any set of points in the unit square that contains the origin, does a set of axis aligned rectangles, one for each point in , exist, such that each of them has a point in as its lower-left corner, they are pairwise interior disjoint, and the total area that they cover is at least 1/2? This question is also known as Freedman's conjecture (conjecturing that such a set of rectangles does exist) and has been open since Allen Freedman posed it in 1969. In this paper, we improve the best known lower bound on the total area that can be covered from 0.09121 to 0.1039. Although this step is small, we introduce new insights that push the limits of this analysis. Our lower bound uses a greedy algorithm with a particular order of the points in . Therefore, it also implies that this greedy algorithm achieves an approximation ratio of 0.1039. We complement the result with an upper bound of 3/4 on the approximation ratio for a natural class of greedy algorithms that includes the one that achieves the lower bound
Erratum: Author Correction: A Lab-in-a-Fiber optofluidic device using droplet microfluidics and laser-induced fluorescence for virus detection (Scientific reports (2022) 12 1 (3539))
No full textCorrection to: Scientific Reports https://doi.org/10.1038/s41598-022-07306-0, published online 03 March 2022
The original version of this Article contained an error in the spelling of the author Ruben R. G. Soares, which was incorrectly given as Ruben G. Soares
- …
