1,721,088 research outputs found
Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time
No full textVassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex graph in time n^{k/2+O(1)}. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via nst/2+O(1)-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω(n^{⌊st/2⌋}) and Ω(n^{⌊k/2⌋}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meet-in-the-middle” exponent st/2 can be beaten and give an algorithm that counts in time n^{0.4547st+O(1)} for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an n-vertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound
Approximation algorithms for the minimum congestion routing problem via k-route flows
Get PDFGiven a directed network G = (V,E) with source and target nodes s and t, respectively, and an integral capacity c_e on each edge e in E, an elementary k-flow is defined as a flow of 1 unit along each of k edge-disjoint s-t paths. A k-route flow, first introduced as a concept by Kishimoto, is defined as a non-negative linear sum of elementary k-flows. In this thesis, the study of k-route flows is extended by presenting efficient algorithms to calculate exact and approximate decompositions of k-route flows into their constituent elementary k-flows.
In addition, such decomposition algorithms are shown to prove useful in developing approximation algorithms for the well-studied Minimum Congestion Routing Problem. Given a directed network G = (V,E), a set of source-sink pairs {(s_1, t_1), ..., (s_l, t_l)}, and an integer k, the goal of the Minimum Congestion Routing Problem is to find k edge-disjoint paths between each pair (s_i, t_i) while minimizing the congestion over all chosen paths (defined as the maximum over all edges of the number of chosen paths that share a single edge). Early applications of randomized rounding introduced by Raghavan and Tompson provided a simple approximation algorithm for the case where k=1, but attempts to achieve similar approximation bounds in the case where k>1 have up until this point required the use of more advanced dependent rounding schemes. Utilizing the k-route flow decomposition algorithms presented in this thesis, we propose approximation algorithms for the Minimum Congestion Routing Problem for the case where k>1 that mimic the straightforward approach of Raghavan and Tompson while achieving identical approximation guarantees. Finally, we implement two variants of the exact k-route flow decomposition algorithm proposed in this thesis, and experimentally compare their performance using flows generated from various graph structures.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo termsThe student, Mark Idleman, accepted the attached license on 2017-07-19 at 15:08.The student, Mark Idleman, submitted this Thesis for approval on 2017-07-19 at 15:22.This Thesis was approved for publication on 2017-07-19 at 16:01.DSpace SAF Submission Ingestion Package generated from Vireo submission #11537 on 2017-09-29 at 11:32:17Made available in DSpace on 2017-09-29T17:57:09Z (GMT). No. of bitstreams: 2
IDLEMAN-THESIS-2017.pdf: 359454 bytes, checksum: 2b852b219d5634faef87647565bccd52 (MD5)
LICENSE.txt: 4209 bytes, checksum: 8ad8e3867802682f3590b552077cabf1 (MD5)
Previous issue date: 2017-07-1
Model-based Sketching and Recovery with Expanders
Get PDFLinear sketching and recovery of sparse vectors with randomly constructed sparse matrices has numerous applications in several areas, including compressive sensing, data stream computing, graph sketching, and combinatorial group testing. This paper considers the same problem with the added twist that the sparse coefficients of the unknown vector exhibit further correlations as determined by a known sparsity model. We prove that exploiting model-based sparsity in recovery provably reduces the sketch size without sacrificing recovery quality. In this context, we present the model-expander iterative hard thresholding algorithm for re- covering model sparse signals from linear sketches obtained via sparse adjacency matrices of expander graphs with rigorous performance guarantees. The main computational cost of our algorithm depends on the difficulty of projecting onto the model-sparse set. For the tree and group-based sparsity models we describe in this paper, such projections can be obtained in linear time. Finally, we provide numerical experiments to illustrate the theoretical results in action.LION
Survivable network design problems with element and vertex connectivity requirements
Get PDFIn this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate this approach in the context of degree-bounded Elem-SNDP and degree-bounded Rooted k-outconnectivity because it helped simplify the proof idea for edge-connectivity SNDP (EC-SNDP), while achieving approximation ratios that were as good as the best known result.
Given a graph G=(V,E) with costs on edges, connectivity requirements between pairs of vertices and degree constraints on vertices, the goal is to compute a minimum cost subgraph H of G that obeys the connectivity requirements and satisfies the degree bounds on the vertices. In the case of element connectivity, connectivity requirement r(uv) between vertices u and v represents the required number of element-disjoint paths between the two vertices. The elements are made up of all the edges and unreliable vertices. This way of defining connectivity models networks where links and nodes can both fail. For Elem-SNDP, our algorithm outputs a solution that has cost at most 3OPT and the degree on each vertex v in the solution is at most 19b(v)+7. In the context of rooted k-outconnectivity problem, connectivity requirement represents the number of internally vertex-disjoint paths between vertices the root r and a vertex v. We extend our approach for Elem-SNDP to the degree-bounded Rooted k-outconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the out-degree on each vertex v in the solution is 19b^+(v)+7. In addition, the in-degree of vertex v is bounded above by b^-(v)+5.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo termsThe student, Shweta Patwa, accepted the attached license on 2017-06-14 at 09:48.The student, Shweta Patwa, submitted this Thesis for approval on 2017-06-14 at 10:17.This Thesis was approved for publication on 2017-06-14 at 16:05.DSpace SAF Submission Ingestion Package generated from Vireo submission #11218 on 2017-09-29 at 11:26:41Made available in DSpace on 2017-09-29T16:37:56Z (GMT). No. of bitstreams: 2
PATWA-THESIS-2017.pdf: 734395 bytes, checksum: d54d7909e2c21ceb2b5033eb7d3de4b3 (MD5)
LICENSE.txt: 4209 bytes, checksum: f98b3c466642a0742a2be9a478aea570 (MD5)
Previous issue date: 2017-06-1
Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity
Get PDFWe study the expressivity and complexity of model checking of linear temporal logic with team semantics (TeamLTL). TeamLTL, despite being a purely modal logic, is capable of defining hyperproperties, i.e., properties which relate multiple execution traces. TeamLTL has been introduced quite recently and only few results are known regarding its expressivity and its model checking problem. We relate the expressivity of TeamLTL to logics for hyperproperties obtained by extending LTL with trace and propositional quantifiers (HyperLTL and HyperQPTL). By doing so, we obtain a number of model checking results for TeamLTL and identify its undecidability frontier. In particular, we show decidability of model checking of the so-called left-flat fragment of any downward closed TeamLTL-extension. Moreover, we establish that the model checking problem of TeamLTL with Boolean disjunction and inclusion atoms is undecidable
Node-weighted prize-collecting survivable network design problems
Get PDFWe consider node-weighted network design problems, in particular
the survivable network design problem SNDP and its
prize-collecting version PC-SNDP. The input consists of a
node-weighted undirected graph and integral connectivity
requirements for each pair of nodes . The goal is
to find a minimum node-weighted subgraph of such that, for
each pair , contains \emph{disjoint} paths
between and . PC-SNDP is a generalization in which the
input also includes a penalty for each pair, and the goal
is to find a subgraph to minimize the sum of the weight of
and the sum of the penalties for all pairs whose connectivity
requirements are not fully satisfied by . We consider three
types of connectivity requirements, \emph{edge-connectivity (EC)},
\emph{element-connectivity (ELC)} and \emph{vertex-connectivity (VC)}.
Let be the maximum requirement. There has been
no non-trivial approximation for node-weighted PC-SNDP for
even in edge-connectivity setup. We describe multiroute-flow
based relaxations for PC-EC-SNDP and PC-ELC-SNDP
and obtain approximation algorithms for PC-SNDP and
PC-ELC-SNDP through them. The approximation ratios we
obtain for PC-EC-SNDP are similar to those that were previously
known for EC-SNDP via combinatorial algorithms. Specifically,
for PC-EC-SNDP (and PC-ELC-SNDP) we obtain an
-approximation in general graphs and an
-approximation in graphs that exclude a fixed minor.
Moreover, based on the approximation algorithm of ELC-SNDP
and the reduction method of Chuzhoy and Khanna~\cite{ChuzhoyK12}
we obtain -approximation for PC-VC-SNDP
which improves to on instances from a minor-closed families of graphs.Item withdrawn by Alexis Thompson ([email protected]) on 2013-07-11T20:48:56Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 5
nw-pc-sndp-thesis.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5)
ms_thesis.bib: 13403 bytes, checksum: d2f7f0fabda6c5947dc32c1dfad862c6 (MD5)
nw-pc-sndp-thesis.tex: 166441 bytes, checksum: bf19e9e3ba79a53f273b70189ead566c (MD5)
figures.zip: 124579 bytes, checksum: 37c7cb93fa408c51336e23a2948773a3 (MD5)
Vakilian_Ali.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5)Made available in DSpace on 2013-08-22T16:40:35Z (GMT). No. of bitstreams: 5
Ali_Vakilian.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5)
figures.zip: 124579 bytes, checksum: 37c7cb93fa408c51336e23a2948773a3 (MD5)
ms_thesis.bib: 13403 bytes, checksum: d2f7f0fabda6c5947dc32c1dfad862c6 (MD5)
nw-pc-sndp-thesis.tex: 166441 bytes, checksum: bf19e9e3ba79a53f273b70189ead566c (MD5)
license.txt: 4062 bytes, checksum: 1061906d751569d27c834d2c94922242 (MD5
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
