7 Search Results for "Swamy, Nikhil"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.1
A Unified Approach to Discrepancy Minimization

Authors: Nikhil Bansal, Aditi Laddha, and Santosh Vempala

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

Abstract
We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.
Cite as

Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A Unified Approach to Discrepancy Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.APPROX/RANDOM.2022.1,
  author =	{Bansal, Nikhil and Laddha, Aditi and Vempala, Santosh},
  title =	{{A Unified Approach to Discrepancy Minimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  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.2022.1},
  URN =		{urn:nbn:de:0030-drops-171238},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.1},
  annote =	{Keywords: Discrepancy theory, smoothed analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.55
A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs

Authors: Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif

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

Abstract
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value f with congestion 4, and a multicut of capacity c such that c ≤ 20 f. This implies a multiflow-multicut gap of 80 and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
Cite as

Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif. A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.APPROX/RANDOM.2022.55,
  author =	{Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena},
  title =	{{A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  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.2022.55},
  URN =		{urn:nbn:de:0030-drops-171774},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.55},
  annote =	{Keywords: Approximation Algorithms, Multicommodity Flow, Multicut}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.67
Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime

Authors: Zachary Friggstad and Chaitanya Swamy

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We investigate a genre of vehicle-routing problems (VRPs), that we call max-reward VRPs, wherein nodes located in a metric space have associated rewards that depend on their visiting times, and we seek a path that earns maximum reward. A prominent problem in this genre is deadline TSP, where nodes have deadlines and we seek a path that visits all nodes by their deadlines and earns maximum reward. Our main result is a constant-factor approximation for deadline TSP running in time O(n^O(log(nΔ))) in metric spaces with integer distances at most Δ. This is the first improvement over the approximation factor of O(log n) due to Bansal et al. [N. Bansal et al., 2004] in over 15 years (but is achieved in super-polynomial time). Our result provides the first concrete indication that log n is unlikely to be a real inapproximability barrier for deadline TSP, and raises the exciting possibility that deadline TSP might admit a polytime constant-factor approximation. At a high level, we obtain our result by carefully guessing an appropriate sequence of O(log (nΔ)) nodes appearing on the optimal path, and finding suitable paths between any two consecutive guessed nodes. We argue that the problem of finding a path between two consecutive guessed nodes can be relaxed to an instance of a special case of deadline TSP called point-to-point (P2P) orienteering. Any approximation algorithm for P2P orienteering can then be utilized in conjunction with either a greedy approach, or an LP-rounding approach, to find a good set of paths overall between every pair of guessed nodes. While concatenating these paths does not immediately yield a feasible solution, we argue that it can be covered by a constant number of feasible solutions. Overall our result therefore provides a novel reduction showing that any α-approximation for P2P orienteering can be leveraged to obtain an O(α)-approximation for deadline TSP in O(n^O(log nΔ)) time. Our results extend to yield the same guarantees (in approximation ratio and running time) for a substantial generalization of deadline TSP, where the reward obtained by a client is given by an arbitrary non-increasing function (specified by a value oracle) of its visiting time. Finally, we discuss applications of our results to variants of deadline TSP, including settings where both end-nodes are specified, nodes have release dates, and orienteering with time windows.
Cite as

Zachary Friggstad and Chaitanya Swamy. Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ICALP.2021.67,
  author =	{Friggstad, Zachary and Swamy, Chaitanya},
  title =	{{Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{67:1--67:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.67},
  URN =		{urn:nbn:de:0030-drops-141369},
  doi =		{10.4230/LIPIcs.ICALP.2021.67},
  annote =	{Keywords: Approximation algorithms, Vehicle routing problems, Deadline TSP, Orienteering}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.81
Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan

Authors: Sharat Ibrahimpur and Chaitanya Swamy

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We consider the minimum-norm load-balancing (MinNormLB) problem, wherein there are n jobs, each of which needs to be assigned to one of m machines, and we are given the processing times {p_{ij}} of the jobs on the machines. We also have a monotone, symmetric norm f:ℝ^m → ℝ_{≥ 0}. We seek an assignment σ of jobs to machines that minimizes the f-norm of the induced load vector load->_σ ∈ ℝ_{≥ 0}^m, where load_σ(i) = ∑_{j:σ(j) = i}p_{ij}. This problem was introduced by [Deeparnab Chakrabarty and Chaitanya Swamy, 2019], and the current-best result for MinNormLB is a (4+ε)-approximation [Deeparnab Chakrabarty and Chaitanya Swamy, 2019]. In the stochastic version of MinNormLB, the job processing times are given by nonnegative random variables X_{ij}, and jobs are independent; the goal is to find an assignment σ that minimizes the expected f-norm of the induced random load vector. We obtain results that (essentially) match the best-known guarantees for deterministic makespan minimization (MinNormLB with 𝓁_∞ norm). For MinNormLB, we obtain a (2+ε)-approximation for unrelated machines, and a PTAS for identical machines. For stochastic MinNormLB, we consider the setting where the X_{ij}s are Poisson random variables, denoted PoisNormLB. Our main result here is a novel and powerful reduction showing that, for any machine environment (e.g., unrelated/identical machines), any α-approximation algorithm for MinNormLB in that machine environment yields a randomized α(1+ε)-approximation for PoisNormLB in that machine environment. Combining this with our results for MinNormLB, we immediately obtain a (2+ε)-approximation for PoisNormLB on unrelated machines, and a PTAS for PoisNormLB on identical machines. The latter result substantially generalizes a PTAS for makespan minimization with Poisson jobs obtained recently by [Anindya De et al., 2020].
Cite as

Sharat Ibrahimpur and Chaitanya Swamy. Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ibrahimpur_et_al:LIPIcs.ICALP.2021.81,
  author =	{Ibrahimpur, Sharat and Swamy, Chaitanya},
  title =	{{Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{81:1--81:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.81},
  URN =		{urn:nbn:de:0030-drops-141504},
  doi =		{10.4230/LIPIcs.ICALP.2021.81},
  annote =	{Keywords: Approximation algorithms, Load balancing, Minimum-norm optimization, LP rounding}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2017.1
Everest: Towards a Verified, Drop-in Replacement of HTTPS

Authors: Karthikeyan Bhargavan, Barry Bond, Antoine Delignat-Lavaud, Cédric Fournet, Chris Hawblitzel, Catalin Hritcu, Samin Ishtiaq, Markulf Kohlweiss, Rustan Leino, Jay Lorch, Kenji Maillard, Jianyang Pan, Bryan Parno, Jonathan Protzenko, Tahina Ramananandro, Ashay Rane, Aseem Rastogi, Nikhil Swamy, Laure Thompson, Peng Wang, Santiago Zanella-Béguelin, and Jean-Karim Zinzindohoué

Published in: LIPIcs, Volume 71, 2nd Summit on Advances in Programming Languages (SNAPL 2017)

Abstract
The HTTPS ecosystem is the foundation on which Internet security is built. At the heart of this ecosystem is the Transport Layer Security (TLS) protocol, which in turn uses the X.509 public-key infrastructure and numerous cryptographic constructions and algorithms. Unfortunately, this ecosystem is extremely brittle, with headline-grabbing attacks and emergency patches many times a year. We describe our ongoing efforts in Everest (The Everest VERified End-to-end Secure Transport) a project that aims to build and deploy a verified version of TLS and other components of HTTPS, replacing the current infrastructure with proven, secure software. Aiming both at full verification and usability, we conduct high-level code-based, game-playing proofs of security on cryptographic implementations that yield efficient, deployable code, at the level of C and assembly. Concretely, we use F*, a dependently typed language for programming, meta-programming, and proving at a high level, while relying on low-level DSLs embedded within F* for programming low-level components when necessary for performance and, sometimes, side-channel resistance. To compose the pieces, we compile all our code to source-like C and assembly, suitable for deployment and integration with existing code bases, as well as audit by independent security experts. Our main results so far include (1) the design of Low*, a subset of F* designed for C-like imperative programming but with high-level verification support, and KreMLin, a compiler that extracts Low* programs to C; (2) an implementation of the TLS-1.3 record layer in Low*, together with a proof of its concrete cryptographic security; (3) Vale, a new DSL for verified assembly language, and several optimized cryptographic primitives proven functionally correct and side-channel resistant. In an early deployment, all our verified software is integrated and deployed within libcurl, a widely used library of networking protocols.
Cite as

Karthikeyan Bhargavan, Barry Bond, Antoine Delignat-Lavaud, Cédric Fournet, Chris Hawblitzel, Catalin Hritcu, Samin Ishtiaq, Markulf Kohlweiss, Rustan Leino, Jay Lorch, Kenji Maillard, Jianyang Pan, Bryan Parno, Jonathan Protzenko, Tahina Ramananandro, Ashay Rane, Aseem Rastogi, Nikhil Swamy, Laure Thompson, Peng Wang, Santiago Zanella-Béguelin, and Jean-Karim Zinzindohoué. Everest: Towards a Verified, Drop-in Replacement of HTTPS. In 2nd Summit on Advances in Programming Languages (SNAPL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 71, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bhargavan_et_al:LIPIcs.SNAPL.2017.1,
  author =	{Bhargavan, Karthikeyan and Bond, Barry and Delignat-Lavaud, Antoine and Fournet, C\'{e}dric and Hawblitzel, Chris and Hritcu, Catalin and Ishtiaq, Samin and Kohlweiss, Markulf and Leino, Rustan and Lorch, Jay and Maillard, Kenji and Pan, Jianyang and Parno, Bryan and Protzenko, Jonathan and Ramananandro, Tahina and Rane, Ashay and Rastogi, Aseem and Swamy, Nikhil and Thompson, Laure and Wang, Peng and Zanella-B\'{e}guelin, Santiago and Zinzindohou\'{e}, Jean-Karim},
  title =	{{Everest: Towards a Verified, Drop-in Replacement of HTTPS}},
  booktitle =	{2nd Summit on Advances in Programming Languages (SNAPL 2017)},
  pages =	{1:1--1:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-032-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{71},
  editor =	{Lerner, Benjamin S. and Bod{\'\i}k, Rastislav and Krishnamurthi, Shriram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2017.1},
  URN =		{urn:nbn:de:0030-drops-71196},
  doi =		{10.4230/LIPIcs.SNAPL.2017.1},
  annote =	{Keywords: Security, Cryptography, Verification, TLS}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.17
Approximation Algorithms for Minimum-Load k-Facility Location

Authors: Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy

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

Abstract
We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facility-location problems. For instance, we show that: (a) even a configuration-style LP-relaxation has a bad integrality gap; and (b) a multi-swap k-median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding the problem, and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.
Cite as

Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy. Approximation Algorithms for Minimum-Load k-Facility Location. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 17-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.APPROX-RANDOM.2014.17,
  author =	{Ahmadian, Sara and Behsaz, Babak and Friggstad, Zachary and Jorati, Amin and Salavatipour, Mohammad R. and Swamy, Chaitanya},
  title =	{{Approximation Algorithms for Minimum-Load k-Facility Location}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{17--33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  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.2014.17},
  URN =		{urn:nbn:de:0030-drops-47154},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.17},
  annote =	{Keywords: approximation algorithms, min-max star cover, facility location, line metrics}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.403
Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications

Authors: Chaitanya Swamy

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

Abstract
We consider the matroid median problem, wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation by Krishnaswamy et al. We illustrate the power and versatility of our techniques by deriving: (a) an 8-approximation for the two-matroid median problem, a generalization of matroid median that we introduce involving two matroids; and (b) a 24-approximation algorithm for matroid median with penalties, which is a vast improvement over the 360-approximation obtained by Krishnaswamy et al. We show that a variety of seemingly disparate facility-location problems considered in the literature -- data placement problem, mobile facility location, k-median forest, metric uniform minimum-latency UFL -- in fact reduce to the matroid median or two-matroid median problems, and thus obtain improved approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.
Cite as

Chaitanya Swamy. Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 403-418, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{swamy:LIPIcs.APPROX-RANDOM.2014.403,
  author =	{Swamy, Chaitanya},
  title =	{{Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{403--418},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  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.2014.403},
  URN =		{urn:nbn:de:0030-drops-47125},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.403},
  annote =	{Keywords: Approximation algorithms, LP rounding, facility location, matroid and submodular polyhedra, knapsack constraints}
}
  • Refine by Author
  • 4 Swamy, Chaitanya
  • 2 Friggstad, Zachary
  • 1 Ahmadian, Sara
  • 1 Bansal, Nikhil
  • 1 Behsaz, Babak
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Discrete optimization
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 3 Approximation algorithms
  • 2 LP rounding
  • 2 facility location
  • 1 Approximation Algorithms
  • 1 Cryptography
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2014
  • 2 2021
  • 2 2022
  • 1 2017

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact