197,064 research outputs found
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
No full textOne of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(T n). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger, 1999]. In comparison, our algorithm implies a bound of O(n M^2) without any dependence on V, or O(n V^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Marek Cygan et al., 2017; Marvin Künnemann et al., 2017].
We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(k m), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider
On the Size and the Approximability of Minimum Temporally Connected Subgraphs
No full textWe consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles
Dr. Duane M. Jackson, Morehouse College, July 2011
No full textThis video is a conversation with Dr. Duane M. Jackson. Dr. Jackson talks about his paper, "Recall and the Serial Position Effect: The Role of Primacy and Recency on Accounting Students' Performance." Jackie Daniel, AUC Woodruff Library, is the interviewer
"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States" By M. Carey.
No full text"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States: containing bried sketches of the moral and political character of those states.
By M. Carey, member of the American philosophical, and of the American Antiquarian Society, and author of The Olive Branch, Cindiciae Hibernicae, essays on banking, on political economy, and on internal improvement.
To which are now added the English editor's comments on the subject; together with Important Advice to Emigrants, and Cautions Against Impositions Practiced in the Outports
Dispelling the Myths Behind First-author Citation Counts
No full textWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Dr. Glendon Swarthout
No full textHosted by Roger M. Busfield, MSU Assistant Professor of Speech and Theater, Meet the Author is designed to introduce a general audience to a contemporary author and their work through in-depth interviews. This episode features a conversation between Dr. Glendon Swarthout, prolific author and English professor at MSU, and assistant professors Sam S. Baskett and Theodore B. Strandness
High-spin states and band terminations in v 49
No full textHigh-spin states in 49 V have been studied through the 28 Si(28 Si, α3p) reaction using the EUROBALL γ-ray detector array. The 49 V level scheme has been extended up to 13.1 MeV including 21 new states. Both negative and positive parity states have been interpreted in the framework of theShell Model. The 27/2− and the 31/2+ band termination states have been observed in agreement with theoretical predictions.Fil: Rodrigues Ferreira Maltez, Dario Pablo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Física; ArgentinaFil: Hojman, Daniel Leonardo. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Lenzi, Silvia M.. Istituto Nazionale Di Fisica Nucleare.; Italia. Università di Padova; ItaliaFil: Cardona, Maria Angelica. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Universidad Nacional de San Martín. Escuela de Ciencia y Tecnología; ArgentinaFil: Fernea, Enrico. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Axiotis, M.. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Beck, C.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Bednarczyk, P.. Polish Academy of Sciences; ArgentinaFil: Bizzetti, P. G.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Bizzetti Sona, A. M.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Della Vedova, F.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Grebosz, J.. Polish Academy of Sciences; ArgentinaFil: Haas, F.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Kmiecik, M.. Polish Academy of Sciences; ArgentinaFil: Maj, A.. Polish Academy of Sciences; ArgentinaFil: Męczyński, W.. Polish Academy of Sciences; ArgentinaFil: Napoli, D. R.. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Nespolo, M.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Papka, P.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Sánchez i Zafra, A.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Styczen, J.. Polish Academy of Sciences; ArgentinaFil: Thummerer, S.. Alfred-Wegener-Institut, Helmholtz-Zentrum für Polar- und Meeresforschung; AlemaniaFil: Ziębliński, M.. Polish Academy of Sciences; Argentin
Simulation of thermal plant optimization and hydraulic aspects of thermal distribution loops for large campuses
No full textFollowing an introduction, the author describes Texas A&M University and its utilities system. After that, the author presents how to construct simulation models for chilled water and heating hot water distribution systems. The simulation model was used in a $2.3 million Ross Street chilled water pipe replacement project at Texas A&M University. A second project conducted at the University of Texas at San Antonio was used as an example to demonstrate how to identify and design an optimal distribution system by using a simulation model. The author found that the minor losses of these closed loop thermal distribution systems are significantly higher than potable water distribution systems. In the second part of the report, the author presents the latest development of software called the Plant Optimization Program, which can simulate cogeneration plant operation, estimate its operation cost and provide optimized operation suggestions. The author also developed detailed simulation models for a gas turbine and heat recovery steam generator and identified significant potential savings. Finally, the author also used a steam turbine as an example to present a multi-regression method on constructing simulation models by using basic statistics and optimization algorithms. This report presents a survey of the author??s working experience at the Energy Systems Laboratory (ESL) at Texas A&M University during the period of January 2002 through March 2004. The purpose of the above work was to allow the author to become familiar with the practice of engineering. The result is that the author knows how to complete a project from start to finish and understands how both technical and nontechnical aspects of a project need to be considered in order to ensure a quality deliverable and bring a project to successful completion. This report concludes that the objectives of the internship were successfully accomplished and that the requirements for the degree of Degree of Engineering have been satisfied
Fast and Simple Modular Subset Sum
No full textWe revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has providedasymptotically optimal algorithms for this problem under the Strong ExponentialTime Hypothesis. Koiliaris and Xu (SODA'17, TALG'19) gave a deterministicalgorithm running in time , which was later improved to randomized time by Axiotis et al. (SODA'19). In this work, wepresent two simple algorithms for the Modular Subset Sum problem running innear-linear time in , both efficiently implementing Bellman's iteration over. The first one is a randomized algorithm running in time, that is based solely on rolling hash and an elementarydata-structure for prefix sums; to illustrate its simplicity we provide a shortand efficient implementation of the algorithm in Python. Our second solution isa deterministic algorithm running in time , thatuses dynamic data structures for string manipulation. We further show that thetechniques developed in this work can also lead to simple algorithms for theAll Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matchingthe asymptotically optimal running time of provided in therecent work of Duan et al. (ICALP'19).<br
- …
