NDLI: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

Please wait, while we are loading the content...

Locality-sensitive hashing without false negatives

New directions in nearest neighbor searching with applications to lattice sieving

Undirected graph exploration with Θ(log log n) pebbles

Phase transitions in group testing

Tight bounds for the distribution-free testing of monotone conjunctions

Designing networks with good equilibria under uncertainty

An improved combinatorial polynomial algorithm for the linear arrow-debreu market

Characterisation of strongly stable matchings

Learning and efficiency in games with dynamic population

The complexity of all-switches strategy improvement

Make-to-order integrated scheduling and distribution

An O(log m)-competitive algorithm for online machine minimization

Online degree-bounded steiner network design

Scheduling parallel DAG jobs online to minimize average flow time

Online pricing with impatient bidders

Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and Min-Cut

Local-on-average distributed tasks

The adversarial noise threshold for distributed protocols

Expanders via local edge flips

An improved distributed algorithm for maximal independent set

Nearly tight oblivious subspace embeddings by trace inequalities

The restricted isometry property of subsampled fourier matrices

Nearly optimal deterministic algorithm for sparse walsh-hadamard transform

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching

Simpler, faster and shorter labels for distances in graphs

Approximate distance oracles for planar graphs with improved query time-space tradeoff

New bounds for approximating extremal distances in undirected graphs

Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs

Deterministic algorithms for submodular maximization problems

Improved approximation algorithms for k-submodular function maximization

Locally adaptive optimization: adaptive seeding for monotone submodular functions

Exact and approximation algorithms for weighted matroid intersection

A fast approximation for maximum weight matroid intersection

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Bounds for random constraint satisfaction problems via spatial coupling

Evolutionary dynamics in finite populations mix rapidly

Random-cluster dynamics in $Z^{2}$

Canonical paths for MCMC: from art to science

Towards optimal algorithms for prediction with expert advice

Sparse approximation via generating point sets

Weighted SGD for $ℓ_{p}$ regression with randomized preconditioning

Non-convex compressed sensing with the sum-of-squares method

Jointly private convex programming

Time vs. information tradeoffs for leader election in anonymous trees

Markovian hitters and the complexity of blind rendezvous

Stabilizing consensus with many opinions

How to scale exponential backoff: constant throughput, polylog access attempts, and robustness

Balanced allocation: patience is not a virtue

Weighted dynamic finger in binary search trees

Faster fully dynamic matchings with small approximation ratios

Dynamic (1 + ε)-approximate matchings: a density-sensitive approach

Dynamic DFS in undirected graphs: breaking the O(m) barrier

On dynamic approximate shortest paths for planar graphs with worst-case costs

Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics

Clustering time series under the fréachet distance

Approximating capacitated k-median with (1 + ε)k open facilities

Simple and fast rounding algorithms for directed and node-weighted multiway cut

Constant factor approximation for subset feedback set problems via a new LP relaxation

Approximating low-stretch spanners

Error amplification for pairwise spanner lower bounds

Better distance preservers and additive spanners

On notions of distortion and an almost minimum spanning tree with constant average distortion

Near-optimal light spanners

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Efficient quantum algorithms for (gapped) group testing and junta testing

Permutation patterns are hard to count

Computing in continuous space with self-assembling polygonal tiles (extended abstract)

Beyond the Richter-Thomassen conjecture

Treetopes and their graphs

Windrose planarity: embedding graphs with direction-constrained edges

Multiscale mapper: topological summarization via codomain covers

Online contention resolution schemes

Finding a stable allocation in polymatroid intersection

An improved approximation guarantee for the maximum budgeted allocation problem

The matching problem has no small symmetric SDP

On the integrality gap of degree-4 sum of squares for planted clique

Linear recognition of almost interval graphs

Subexponential parameterized algorithm for interval completion

lower bounds for the parameterized complexity of minimum fill-in and other completion problems

Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee

Directed multicut is W[1]-hard, even for four terminal pairs

An efficient algorithm for computing high-quality paths amid polygonal obstacles

Approximating the k-level in three-dimensional plane arrangements

Improved deterministic algorithms for linear programming in low dimensions

A fast and simple algorithm for computing approximate euclidean minimum spanning trees

Persistent homology and nested dissection

Deterministic APSP, orthogonal vectors, and more: quickly derandomizing razborov-smolensky

Subtree isomorphism revisited

Higher lower bounds from the 3SUM conjecture

A faster subquadratic algorithm for finding outlier correlations

Algorithmic complexity of power law networks

Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

Maximum matchings in dynamic graph streams and the simultaneous communication model

Incidence geometries and the pass complexity of semi-streaming set cover

Clustering problems on sliding windows

Gowers norm, function limits, and parameter estimation

On the economic efficiency of the combinatorial clock auction

Approximately efficient double auctions with strong budget balance

Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

On the complexity of dynamic mechanism design

Simple pricing schemes for consumers with evolving values

On approximating strip packing with a better ratio than 3/2

Packing small vectors

Approximation schemes for machine scheduling with resource (in-)dependent processing times

Integrality gaps and approximation algorithms for dispersers and bipartite expanders

Improved approximation for vector bin packing

Connectivity in bridge-addable graph classes: the mcdiarmid-steger-welsh conjecture

Recovery and rigidity in a regular stochastic block model

Distance in the forest fire model how far are you from eve?

Species trees from gene trees despite a high rate of lateral genetic transfer: a tight bound

The power of two choices with simple tabulation

Tight bounds for graph homomorphism and subgraph isomorphism

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

Discovering archipelagos of tractability for constraint satisfaction and counting

Blocking optimal k-arborescences

Constructive algorithm for path-width of matroids

Approximation of non-boolean 2CSP

An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra

Nearly optimal NP-hardness of unique coverage

Algorithms and adaptivity gaps for stochastic probing

Discrete gaussian sampling reduces to CVP and SVP

An algorithmic hypergraph regularity lemma

Obstructions for three-coloring graphs with one forbidden induced subgraph

Independence and efficient domination on $P_{6}-free$ graphs

Sparsity and dimension

Finding perfect matchings in bipartite hypergraphs

Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver

How to round subspaces: a new spectral clustering algorithm

Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

Approximate undirected maximum flows in o(mpolylog(n)) time

Natural algorithms for flow problems

Efficient low-redundancy codes for correcting multiple deletions

An improved bound on the fraction of correctable deletions

Communication complexity of permutation-invariant functions

Towards optimal deterministic coding for interactive communication

Robust positioning patterns

Sampling on lattices with free boundary conditions using randomized extensions

On the switch markov chain for perfect matchings

Partial resampling to approximate covering integer programs

Algorithmic and enumerative aspects of the moser-tardos distribution

Focused stochastic local search and the lovász local lemma

The k-mismatch problem revisited

Range predecessor and lempel-ziv parsing

Communication with contextual uncertainty

Weak duality for packing edge-disjoint odd (u, v)-trails

On the maximum quartet distance between phylogenetic trees

Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

Content Provider	ACM Digital Library
Author	Chitnis, Rajesh Cormode, Graham Esfandiari, Hossein Monemizadeh, Morteza Hajiaghayi, MohammadTaghi Vorotnikova, Sofya McGregor, Andrew
Abstract	In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: • Matching: Our main result for matchings is that there exists an $Õ(k^{2})$ space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used Õ(kn) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. We also show that there exists an $Õ(n^{2}/α^{3})$ space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first non-trivial results in the dynamic setting. • Vertex Cover and Hitting Set: There exists an $Õ(k^{d})$ space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. The case d = 2 corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including b-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.
Starting Page	1326
Ending Page	1344
Page Count	19
File Format	PDF
ISBN	9781611974331
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-10
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in