17 research outputs found
On the Parameterized Complexity of Multiway Near-Separator
Get PDFWe study a new graph separation problem called Multiway Near-Separator. Given an undirected graph G, integer k, and terminal set T ⊆ V(G), it asks whether there is a vertex set S ⊆ V(G) ⧵ T of size at most k such that in graph G-S, no pair of distinct terminals can be connected by two pairwise internally vertex-disjoint paths. Hence each terminal pair can be separated in G-S by removing at most one vertex. The problem is therefore a generalization of (Node) Multiway Cut, which asks for a vertex set for which each terminal is in a different component of G-S. We develop a fixed-parameter tractable algorithm for Multiway Near-Separator running in time 2^{(k log k)} ⋅ n^{(1)}. Our algorithm is based on a new pushing lemma for solutions with respect to important separators, along with two problem-specific ingredients. The first is a polynomial-time subroutine to reduce the number of terminals in the instance to a polynomial in the solution size k plus the size of a given suboptimal solution. The second is a polynomial-time algorithm that, given a graph G and terminal set T ⊆ V(G) along with a single vertex x ∈ V(G) that forms a multiway near-separator, computes a 14-approximation for the problem of finding a multiway near-separator not containing x
Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs
Get PDFWe study the kernelization complexity of the Weighted H-Packing problem on sparse graphs. For a fixed connected graph H, in the Weighted H-Packing problem the input is a graph G, a vertex-weight function w: V (G) → N, and positive integers k, t. The question is whether there exist k vertex-disjoint subgraphs H 1, ⋯, H k of G such that H i is isomorphic to H for each i ∈ [k] and the total weight of these k · |V (H)| vertices is at least t. It is known that the (unweighted) H-Packing problem admits a kernel with O(k |V (H)|-1) vertices on general graphs, and a linear kernel on planar graphs and graphs of bounded genus. In this work, we focus on case that H is a clique on h ≥ 3 vertices (which captures Triangle Packing) and present a linear-vertex kernel for Weighted Kh-Packing on graphs of bounded expansion, along with a kernel with O(k 1+ϵ) vertices on nowhere-dense graphs for all ϵ > 0. To obtain these results, we combine two powerful ingredients in a novel way: the Erdos-Rado Sunflower lemma and the theory of sparsity.</p
On the Hardness of Compressing Weights
Get PDFWe investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted graph and the goal is to detect a clique of total weight equal to a prescribed value. We show that the weighted variant, parameterized by the number of vertices n, is significantly harder than the unweighted problem by presenting an (n^{3 - ε}) lower bound on the size of the kernel, under the assumption that NP ̸ ⊆ coNP/poly. This lower bound is essentially tight: we show that we can reduce the problem to the case with weights bounded by 2^(n), which yields a randomized kernel of (n³) bits.
We generalize these results to the weighted d-Uniform Hyperclique problem, Subset Sum, and weighted variants of Boolean Constraint Satisfaction Problems (CSPs). We also study weighted minimization problems and show that weight compression is easier when we only want to {preserve the collection of} optimal solutions. Namely, we show that for node-weighted Vertex Cover on bipartite graphs it is possible to maintain the set of optimal solutions using integer weights from the range [1, n], but if we want to maintain the ordering of the weights of all inclusion-minimal solutions, then weights as large as 2^Ω(n) are necessary
Video multicast over wireless local area networks
No full textVideo multicast services over wireless media are expected to grow in importance over the next few years. Multicasting over wireless networks is complicated by the fact that wireless links are error-prone and time varying. In multicast scenarios using the 802.11 wireless LAN protocol, multiple receivers experience widely varying channel conditions and the link layer protocol does not retransmit erroneous or lost packets, potentially resulting in poor video quality. Therefore, it is a key requirement to support quality of service for all the receivers of the multicast video in the desired coverage area while efficiently utilizing the available wireless LAN resources.
In this thesis, we investigate some of the aspects of reliable video multicast over WLANs. We design, implement and evaluate multi-group hybrid ARQ (MHARQ), a new and improved adaptive system for reliable video multicast. MHARQ combines the advantages of receiver-driven staggered FEC and hybrid ARQ schemes to compensate the large dynamic range of WLAN channels and to achieve high reliability, scalability and wireless bandwidth efficiency for video multicast. The FEC packets generated by a cross-packet FEC code are divided into multiple streams according to the pre-configured overhead and are transmitted in different multiple IP multicast groups. Certain FEC streams are delayed from the original video stream. The receivers dynamically join/leave the FEC multicast groups based on the channel conditions. For efficient utilization of WLAN bandwidth, FEC data for a multicast group would not be transmitted by the APs in wireless networks if no receiver joins this group. The time shift between the video stream and the FEC streams introduces temporal diversity and compensates for the client join delay and handoff interruption. In addition, when delayed FEC packets are not enough to recover the lost packets, the receivers can send a hybrid ARQ request to the video server. We design a channel estimation algorithm for a receiver to dynamically determine the delayed FEC multicast groups to join and/or send ARQ NACK to request for retransmission.
Using the ORBIT radio grid testbed, we have investigated the performance of the proposed MHARQ system with various numbers of users per AP and different numbers of APs per video server. It is demonstrated via real system implementation on ORBIT that MHARQ improves wireless bandwidth efficiency and scalability for reliable video multicast, compared with existing reliable multicast schemes. The experience and insight obtained from implementation are discussed as well.M.S.Includes bibliographical references (p. 55-56)
A Review of Smart Protection Solutions for Future Power Systems
No full textThe growing demand for electricity and the importance of decarbonization have forced to transition from fossil fuels to sustainable sources of energy like wind and solar. Currently, the universal power mix remains dominated by fossil fuels but plans are in motion to achieve the target set for the upcoming years. It involves grid expansion and the addition of new elements in the form of Distributed Energy Resources(DERs). This has an influence on the performance of the complete power system. To allow an increasing penetration level ofDG(Distributed Generations) without causing protection problems or unacceptable power flows and fault levels, the impact of DG has to be researched for a secured future grid.The protection system of the power system is an aspect that will be significantly affected by the continuous integration of Distributed generation sources. For this reason, it is crucial to develop and validate smart protection solutions for future power systems in order to avoid catastrophic blackouts. In order to overcome the shortcomings, Synchrophasor systems can be used for real-time wide area protection and control. The real-time implementation reflects a smart protection scheme, using smart hardware such as a Phasor measurement Unit (PMU). By developing a suitable algorithm that can be used for decision-makingin case of an event on the transmission lines. It coherently helps in faster restoration of the transmission lines operation. Smart protection solutions will help in strengthening the protection system and will allow more flexibility in the coming years.Electrical Engineering | Sustainable Energy Technolog
Patentopia: A multi-stage patent extraction platform with disambiguation for certain semantic challenges
No full textBibliographic name disambiguation is an major semantic challenge, but critical to social sciences studies of important intellectual assets. Here we contribute to innovation research in several ways. We show a significant synonym problem in author names and discuss how a pre-processing heuristic step standardizing name variants helps, but homonyms generated with Chinese names are particularly difficult to resolve and manifest in an associated location list. Here we identify a new phenomenon of "onomastic profusion," the frequent use of certain words in firm names for semantic reasons that can confound disambiguation clustering algorithms. We illustrate these concerns with Patentopia, our customized platform accessing the PatentsView portal for the United States Patent and Trademark Office database and available for free academic use. This multi-stage system uses heuristics in concert with the PatentsView clustering process and reports meta-data to further assist analysis. As highly relevant use cases, we illustrate system performance with data derived from two important public innovation programs, I-Corps and Small Business Innovation Research (SBIR), and we close with implications for bibliometric analysis of current patent data.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Delft Centre for Entrepreneurshi
Deterministic bibliometric disambiguation challenges in company names
No full textPeer-reviewed publications and patents serve as important signatures of knowledge generation, and therefore the authors and their organizations can represent agents of intellectual transformation. Accurate tracking of these players enables scholars to follow knowledge evolution. However, while author name disambiguation has been discussed extensively, less is known about the impact of organization name on bibliometric studies. We expand here on the recently defined phenomenon of onomastic profusion, high-frequency words used in organization names for semantic reasons, and thus contributing a non-random source of error to bibliographic studies. We use the Small Business Innovation Research (SBIR) Phase I awardees of the National Aeronautics and Space Administration (NASA) as a use case in the field of engineering innovation. We find that firms in California or Massachusetts experience a six percent decrease in the likelihood of using the word Technologies in their names. Furthermore, use of the words Research and Science is linked to doubling the number of awards. We illustrate that, in aggregate, firms executing rational strategic naming decisions can create deterministic bibliometric challenges.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Delft Centre for Entrepreneurshi
