89 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
Algorithms for Subset Sum using linear sketching
No full textThesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from PDF version of thesis.Includes bibliographical references (pages 41-43).Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = + [infinity symbol]) with ties to additive combinatorics and cryptography. The non-modular case was long known to be NP-complete but to admit pseudo-polynomial time algorithms and, recently, algorithms running in near-linear pseudo-polynomial time were developed [9, 211. For the modular case, however, the best known algorithm by Koiliaris and Xu [21] runs in time 0̃ (m⁵/⁴). In this thesis we tackle this problem by devising a faster algorithm for the Modular Subset Sum problem, running in 0̃(m) randomized time, which matches a recent conditional lower bound of [1] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the "textbook" Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for exact combinatorial problems in an offline setting.by Kyriakos Axiotis.S.M.S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc
Charged fermions and strong cosmic censorship
No full textIt was recently shown that the Strong Cosmic Censorship conjecture might be violated for near-extremally-charged black holes in de Sitter space. Here, we extend our study to charged fermionic fields in the exterior of Reissner-Nordstrom-de Sitter black holes. We identify three families of modes; one related to the photon sphere, a second related to the de Sitter horizon and a third which dominates near extremality. We show that for near-extremally-charged black holes there is a critical fermionic charge below which Strong Cosmic Censorship may potentially be violated. Surprisingly enough, as one approaches extremality even more, violation of Strong Cosmic Censorship may occur even beyond the critical fermionic charge. (C) 2019 The Author. Published by Elsevier B.V
Despite Praise: Techniques of Paradoxology and Paradoxography in the Work of Kyriakos Charalambides
No full textCritics have often said that Kyriakos Charalambides’ poetry is hard and challenging even for the most cultivated and well-read reader. The author of the article examines the techniques of rhetoric style with which the poet orchestrates his inspirations: parentheses, stereotypical, corrective and introductory phrases, innuendoes, direct and indirect questions, comic scenes, etc.Critics have often said that Kyriakos Charalambides’ poetry is hard and challenging even for the most cultivated and well-read reader. The author of the article examines the techniques of rhetoric style with which the poet orchestrates his inspirations: parentheses, stereotypical, corrective and introductory phrases, innuendoes, direct and indirect questions, comic scenes, etc.À plusieurs reprises la critique a signalé que la poésie de Kyriakos Charalambidis présente beaucoup de résistances et des difficultés même pour les lecteurs les plus initiés. Dans cet article sont examinées des techniques rhétoriques de style à l’aide desquelles le poète orchestre ses inspirations poétiques: des parenthèses, des phrases stéréotypées, correctives, et annonciatrices, des sous-entendus, des questions directes et indirectes, des scènes comiques, etc
Kyriakos Mitsotakis: The Permanent Campaign Prime Minister
No full textThis chapter discusses the political background of Kyriakos Mitsotakis and evaluates his permanent campaigning at a time of the Covid-19 crisis and the resulting economic one. In particular, it examines his communication strategy from the perspective of the three categories of the permanent campaign indicators (capacity building and strategy, paid and owned media as well as earned media). It finds that Mitsotakis has so far applied permanent campaigning, to a greater degree, than any of his predecessors and thus can be considered as the ‘permanent campaign prime minister’. Moreover, he has put emphasis on all three sets of this communication strategy: capacity building and strategy, paid and owned media as well as earned media. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG
Flows, Submodularity, Sparsity, and Beyond: Continuous Optimization Insights for Discrete Problems
No full textIn this thesis we build on connections between discrete and continuous optimization. In the first part of the thesis we propose faster second-order convex optimization algorithms for classical graph algorithmic problems. Our main contribution is to show that the runtime of interior point methods is closely connected to spectral connectivity notions in the underlying graph, such as electrical conductance and effective resistance. We explore these connections along two orthogonal directions: Making manual interventions to the graph to improve connectivity, or keeping track of connectivity so as to make faster updates. These ideas lead to the first runtime improvement for the minimum cost flow problem in more than 10 years, as well as faster algorithms for problems like negative-weight shortest path and minimum cost perfect matching.
In the second part of the thesis, we investigate efficient optimization algorithms for problems relevant to machine learning that have some discrete element, such as sparse or low rank structure. We introduce a new technique, called adaptive regularization, which eliminates the sparsity performance degradation caused by ℓ₂ projections onto structured non-convex domains, like the set of sparse vectors or low rank matrices. This leads to improving the sparsity guarantee of one of the most well known sparse optimization algorithms, IHT.Ph.D
The sustainable growth paradigm : implications for technology and policy
No full textThesis (S.M. in Technology and Policy)--Massachusetts Institute of Technology, Engineering Systems Division, Technology and Policy Program, 2009.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Includes bibliographical references (leaves 102-109).While some scholars continue to insist that the concept of sustainability is vague and unwieldy, this thesis seeks to explore multidimensional elements of sustainability and seeks to offer an integrative, transdisciplinary approach to policy design for its attainment. Sustainability and the related concepts of development, globalization, and economic and environmental justice are interwoven with technological, social and institutional change, and with trade as drivers of the transformation of industrial and industrializing societies. The discussion begins by an analysis of the dominant existing models of economic growth and innovation and advances to the effects of economic growth on sustainability. Included is an analysis of the limits of the GDP growth paradigm, the effects of growth on the developed and the developing world and the relationship between economic growth and ecological collapse. The focus of analysis then shifts from the domestic to the international. Trade and the International Financial System are examined both with respect to their primary theories and characteristics, but also in relation to their effects to sustainability. The discussion is then concluded by an examination of the different policy options and analytical tools that could be employed for a transition to a more sustainable economic model.by Kyriakos Pierrakakis.S.M.in Technology and Polic
Performance of Regularization for Sparse Convex Optimization
No full textDespite widespread adoption in practice, guarantees for the LASSO and Group
LASSO are strikingly lacking in settings beyond statistical problems, and these
algorithms are usually considered to be a heuristic in the context of sparse
convex optimization on deterministic inputs. We give the first recovery
guarantees for the Group LASSO for sparse convex optimization with
vector-valued features. We show that if a sufficiently large Group LASSO
regularization is applied when minimizing a strictly convex function , then
the minimizer is a sparse vector supported on vector-valued features with the
largest norm of the gradient. Thus, repeating this procedure selects
the same set of features as the Orthogonal Matching Pursuit algorithm, which
admits recovery guarantees for any function with restricted strong
convexity and smoothness via weak submodularity arguments. This answers open
questions of Tibshirani et al. and Yasuda et al. Our result is the first to
theoretically explain the empirical success of the Group LASSO for convex
functions under general input instances assuming only restricted strong
convexity and smoothness. Our result also generalizes provable guarantees for
the Sequential Attention algorithm, which is a feature selection algorithm
inspired by the attention mechanism proposed by Yasuda et al.
As an application of our result, we give new results for the column subset
selection problem, which is well-studied when the loss is the Frobenius norm or
other entrywise matrix losses. We give the first result for general loss
functions for this problem that requires only restricted strong convexity and
smoothness
- …
