10 Search Results for "Harris, David G."


Document
A Faster Algorithm for Vertex Cover Parameterized by Solution Size

Authors: David G. Harris and N. S. Narayanaswamy

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)


Abstract
We describe a new algorithm for vertex cover with runtime O^*(1.25284^k), where k is the size of the desired solution and O^* hides polynomial factors in the input size. This improves over the previous runtime of O^*(1.2738^k) due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a measure which simultaneously tracks k as well as the optimal value λ of the vertex cover LP relaxation. This allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both k and μ = k - λ are decreased at each step. There can be local obstructions in the graph that prevent μ from decreasing in this process; we develop a number of novel branching steps to handle these situations.

Cite as

David G. Harris and N. S. Narayanaswamy. A Faster Algorithm for Vertex Cover Parameterized by Solution Size. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.STACS.2024.40,
  author =	{Harris, David G. and Narayanaswamy, N. S.},
  title =	{{A Faster Algorithm for Vertex Cover Parameterized by Solution Size}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.40},
  URN =		{urn:nbn:de:0030-drops-197508},
  doi =		{10.4230/LIPIcs.STACS.2024.40},
  annote =	{Keywords: Vertex cover, FPT, Graph algorithm}
}
Document
Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication

Authors: David G. Harris

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
Karppa & Kaski (2019) proposed a novel type of "broken" or "opportunistic" multiplication algorithm, based on a variant of Strassen’s algorithm, and used this to develop new algorithms for Boolean matrix multiplication, among other tasks. For instance, their algorithm can compute Boolean matrix multiplication in O(n^log₂(6+6/7) log n) = O(n^2.778) time. While faster matrix multiplication algorithms exist asymptotically, in practice most such algorithms are infeasible for practical problems. We describe an alternative way to use the broken matrix multiplication algorithm to approximately compute matrix multiplication, either for real-valued matrices or Boolean matrices. In brief, instead of running multiple iterations of the broken algorithm on the original input matrix, we form a new larger matrix by sampling and run a single iteration of the broken algorithm. Asymptotically, the resulting algorithm has runtime O(n^{(3 log6)/log7} log n) ≤ O(n^2.763), a slight improvement of Karppa-Kaski’s algorithm. Since the goal is to obtain new practical matrix-multiplication algorithms, these asymptotic runtime bounds are not directly useful. We estimate the runtime for our algorithm for some sample problems which are at the upper limits of practical algorithms; it appears that for these parameters, further optimizations are still needed to make our algorithm competitive.

Cite as

David G. Harris. Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{harris:LIPIcs.ESA.2023.57,
  author =	{Harris, David G.},
  title =	{{Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.57},
  URN =		{urn:nbn:de:0030-drops-187104},
  doi =		{10.4230/LIPIcs.ESA.2023.57},
  annote =	{Keywords: Matrix multiplication, Boolean matrix multiplication, Strassen’s algorithmkeyword}
}
Document
Track A: Algorithms, Complexity and Games
Parameter Estimation for Gibbs Distributions

Authors: David G. Harris and Vladimir Kolmogorov

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n]. The partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min) We develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.

Cite as

David G. Harris and Vladimir Kolmogorov. Parameter Estimation for Gibbs Distributions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 72:1-72:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.ICALP.2023.72,
  author =	{Harris, David G. and Kolmogorov, Vladimir},
  title =	{{Parameter Estimation for Gibbs Distributions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{72:1--72:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.72},
  URN =		{urn:nbn:de:0030-drops-181246},
  doi =		{10.4230/LIPIcs.ICALP.2023.72},
  annote =	{Keywords: Gibbs distribution, sampling}
}
Document
APPROX
Approximating Two-Stage Stochastic Supplier Problems

Authors: Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)


Abstract
The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints. Our eventual goal is to provide results for supplier problems in the most general distributional setting, where there is only black-box access to the underlying distribution. To that end, we follow a two-step approach. First, we develop algorithms for a restricted version of each problem, in which all possible scenarios are explicitly provided; second, we employ a novel scenario-discarding variant of the standard Sample Average Approximation (SAA) method, in which we crucially exploit properties of the restricted-case algorithms. We finally note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.

Cite as

Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti. Approximating Two-Stage Stochastic Supplier Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{brubach_et_al:LIPIcs.APPROX/RANDOM.2021.23,
  author =	{Brubach, Brian and Grammel, Nathaniel and Harris, David G. and Srinivasan, Aravind and Tsepenekas, Leonidas and Vullikanti, Anil},
  title =	{{Approximating Two-Stage Stochastic Supplier Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.23},
  URN =		{urn:nbn:de:0030-drops-147163},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.23},
  annote =	{Keywords: Approximation Algorithms, Stochastic Optimization, Two-Stage Recourse Model, Clustering Problems, Knapsack Supplier}
}
Document
RANDOM
A New Notion of Commutativity for the Algorithmic Lovász Local Lemma

Authors: David G. Harris, Fotis Iliopoulos, and Vladimir Kolmogorov

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)


Abstract
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser & Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for convergence, many other natural questions can be asked about algorithms; for instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?". These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.

Cite as

David G. Harris, Fotis Iliopoulos, and Vladimir Kolmogorov. A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 31:1-31:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.APPROX/RANDOM.2021.31,
  author =	{Harris, David G. and Iliopoulos, Fotis and Kolmogorov, Vladimir},
  title =	{{A New Notion of Commutativity for the Algorithmic Lov\'{a}sz Local Lemma}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{31:1--31:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.31},
  URN =		{urn:nbn:de:0030-drops-147244},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.31},
  annote =	{Keywords: Lov\'{a}sz Local Lemma, Resampling, Moser-Tardos algorithm, latin transversal, commutativity}
}
Document
Distributed Dense Subgraph Detection and Low Outdegree Orientation

Authors: Hsin-Hao Su and Hoa T. Vu

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
The densest subgraph problem, introduced in the 80s by Picard and Queyranne [Networks 1982] as well as Goldberg [Tech. Report 1984], is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. Suppose G = (V,E) is the underlying network as well as the input graph. Let D denote the density of the maximum density subgraph of G. Our main results are as follows. - Given a value D̃ ≤ D and 0 < ε < 1, we show that a subgraph with density at least (1-ε)D̃ can be identified deterministically in O((log n) / ε) rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an O(log n) factor. In the CONGEST~ model, we show that such a subgraph can be identified in O((log³ n) / ε³) rounds with high probability. Our techniques also lead to an O(diameter + (log⁴ n)/ε⁴)-round algorithm that yields a 1-ε approximation to the densest subgraph. This improves upon the previous O(diameter /ε ⋅ log n)-round algorithm by Das Sarma et al. [DISC 2012] that only yields a 1/2-ε approximation. - Given an integer D̃ ≥ D and Ω(1/D̃) < ε < 1/4, we give a deterministic, Õ((log² n) /ε²)-round algorithm in the CONGEST~ model that computes an orientation where the outdegree of every vertex is upper bounded by (1+ε)D̃. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in Õ((log⁶ n)/ ε⁴) rounds and Õ((log³ n) /ε³) rounds respectively and only work in the LOCAL model.

Cite as

Hsin-Hao Su and Hoa T. Vu. Distributed Dense Subgraph Detection and Low Outdegree Orientation. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{su_et_al:LIPIcs.DISC.2020.15,
  author =	{Su, Hsin-Hao and Vu, Hoa T.},
  title =	{{Distributed Dense Subgraph Detection and Low Outdegree Orientation}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.15},
  URN =		{urn:nbn:de:0030-drops-130938},
  doi =		{10.4230/LIPIcs.DISC.2020.15},
  annote =	{Keywords: Distributed Algorithms, Network Algorithms}
}
Document
RANDOM
Palette Sparsification Beyond (Δ+1) Vertex Coloring

Authors: Noga Alon and Sepehr Assadi

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every n-vertex graph G with maximum degree Δ, sampling O(log n) colors per each vertex independently from Δ+1 colors almost certainly allows for proper coloring of G from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for (Δ+1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we focus on palette sparsification beyond (Δ+1) coloring, in both regimes when the number of available colors is much larger than (Δ+1), and when it is much smaller. In particular, - We prove that for (1+ε) Δ coloring, sampling only O_ε(√{log n}) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1+ε) Δ and (Δ+1) coloring in the context of palette sparsification. - A natural family of graphs with chromatic number much smaller than (Δ+1) are triangle-free graphs which are O(Δ/ln Δ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(Δ^γ + √{log n}) colors per vertex is sufficient and necessary to obtain a proper O_γ(Δ/ln Δ) coloring of triangle-free graphs. - We also consider the "local version" of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling O_ε(log n) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1+ε) ⋅ deg(v) arbitrary colors, or even only deg(v)+1 colors when the lists are the sets {1,…,deg(v)+1}. Our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.

Cite as

Noga Alon and Sepehr Assadi. Palette Sparsification Beyond (Δ+1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.APPROX/RANDOM.2020.6,
  author =	{Alon, Noga and Assadi, Sepehr},
  title =	{{Palette Sparsification Beyond (\Delta+1) Vertex Coloring}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.6},
  URN =		{urn:nbn:de:0030-drops-126096},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.6},
  annote =	{Keywords: Graph coloring, palette sparsification, sublinear algorithms, list-coloring}
}
Document
Distributed Coloring of Graphs with an Optimal Number of Colors

Authors: Étienne Bamas and Louis Esperet

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on coloring graphs of maximum degree Delta with at most Delta+1 colors (or Delta colors when some simple obstructions are forbidden). When Delta is sufficiently large and c >= Delta-k_Delta+1, for some integer k_Delta ~~ sqrt{Delta}-2, we give a distributed algorithm that given a c-colorable graph G of maximum degree Delta, finds a c-coloring of G in min{O((log Delta)^{13/12}log n), 2^{O(log Delta+sqrt{log log n})}} rounds, with high probability. The lower bound Delta-k_Delta+1 is best possible in the sense that for infinitely many values of Delta, we prove that when chi(G) <= Delta-k_Delta, finding an optimal coloring of G requires Omega(n) rounds. Our proof is a light adaptation of a remarkable result of Molloy and Reed, who proved that for Delta large enough, for any c >= Delta-k_Delta deciding whether chi(G) <= c is in P, while Embden-Weinert et al. proved that for c <= Delta-k_Delta-1, the same problem is NP-complete. Note that the sequential and distributed thresholds differ by one. Our first result covers the case where the chromatic number of the graph ranges between Delta-sqrt{Delta} and Delta+1. Our second result covers a larger range, but gives a weaker bound on the number of colors: For any sufficiently large Delta, and Omega(log Delta) <= k <= Delta/100, we prove that every graph of maximum degree Delta and clique number at most Delta-k can be efficiently colored with at most Delta-epsilon k colors, for some absolute constant epsilon >0, with a randomized algorithm running in O(log n/log log n) rounds with high probability.

Cite as

Étienne Bamas and Louis Esperet. Distributed Coloring of Graphs with an Optimal Number of Colors. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bamas_et_al:LIPIcs.STACS.2019.10,
  author =	{Bamas, \'{E}tienne and Esperet, Louis},
  title =	{{Distributed Coloring of Graphs with an Optimal Number of Colors}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.10},
  URN =		{urn:nbn:de:0030-drops-102496},
  doi =		{10.4230/LIPIcs.STACS.2019.10},
  annote =	{Keywords: Graph coloring, distributed algorithm, maximum degree}
}
Document
A Lottery Model for Center-Type Problems with Outliers

Authors: David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)


Abstract
In this paper, we give tight approximation algorithms for the k-center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients could always be considered as outliers. To address this issue, we introduce a lottery model in which each client is allowed to submit a parameter indicating the lower-bound on the probability that it should be covered and we look for a random solution that satisfies all the given requests. Out techniques include a randomized rounding procedure to round a point inside a matroid intersection polytope to a basis plus at most one extra item such that all marginal probabilities are preserved and such that a certain linear function of the variables does not decrease in the process with probability one.

Cite as

David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. A Lottery Model for Center-Type Problems with Outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.APPROX-RANDOM.2017.10,
  author =	{Harris, David G. and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa},
  title =	{{A Lottery Model for Center-Type Problems with Outliers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.10},
  URN =		{urn:nbn:de:0030-drops-75596},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.10},
  annote =	{Keywords: approximation algorithms, randomized rounding, clustering problems}
}
Document
Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs

Authors: David G. Harris and Francis Sullivan

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
The all-terminal reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We show upper bounds on the relative error of three sequential importance sampling algorithms. We use these to create a hybrid algorithm, which selects the best SIS algorithm for a particular graph G and particular coefficient of the polynomial. This hybrid algorithm is particularly effective when G has low degree. For graphs of average degree < 11, it is the fastest known algorithm; for graphs of average degree <= 45 it is the fastest known polynomial-space algorithm. For example, when a graph has average degree 3, this algorithm estimates to error epsilon in time O(1.26^n * epsilon^{-2}). Although the algorithm may take exponential time, in practice it can have good performance even on medium-scale graphs. We provide experimental results that show quite practical performance on graphs with hundreds of vertices and thousands of edges. By contrast, alternative algorithms are either not rigorous or are completely impractical for such large graphs.

Cite as

David G. Harris and Francis Sullivan. Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 323-340, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.APPROX-RANDOM.2015.323,
  author =	{Harris, David G. and Sullivan, Francis},
  title =	{{Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{323--340},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.323},
  URN =		{urn:nbn:de:0030-drops-53101},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.323},
  annote =	{Keywords: All-terminal reliability, sequential importance sampling}
}
  • Refine by Author
  • 7 Harris, David G.
  • 2 Kolmogorov, Vladimir
  • 2 Srinivasan, Aravind
  • 1 Alon, Noga
  • 1 Assadi, Sepehr
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Graph coloring
  • 2 Mathematics of computing → Probabilistic algorithms
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 2 Graph coloring
  • 1 All-terminal reliability
  • 1 Approximation Algorithms
  • 1 Boolean matrix multiplication
  • 1 Clustering Problems
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2020
  • 2 2021
  • 2 2023
  • 1 2015
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail