2 Search Results for "Naserasr, Reza"

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.18

A Randomized Rounding Approach for DAG Edge Deletion

Authors: Sina Kalantarzadeh, Nathan Klein, and Victor Reis

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

Abstract

In the DAG Edge Deletion problem, we are given an edge-weighted directed acyclic graph and a parameter k, and the goal is to delete the minimum weight set of edges so that the resulting graph has no paths of length k. This problem, which has applications to scheduling, was introduced in 2015 by Kenkre, Pandit, Purohit, and Saket. They gave a k-approximation and showed that it is UGC-Hard to approximate better than ⌊0.5k⌋ for any constant k ≥ 4 using a work of Svensson from 2012. The approximation ratio was improved to 2/3(k+1) by Klein and Wexler in 2016. In this work, we introduce a randomized rounding framework based on distributions over vertex labels in [0,1]. The most natural distribution is to sample labels independently from the uniform distribution over [0,1]. We show this leads to a (2-√2)(k+1) ≈ 0.585(k+1)-approximation. By using a modified (but still independent) label distribution, we obtain a 0.549(k+1)-approximation for the problem, as well as show that no independent distribution over labels can improve our analysis to below 0.542(k+1). Finally, we show a 0.5(k+1)-approximation for bipartite graphs and for instances with structured LP solutions. Whether this ratio can be obtained in general is open.

Cite as

Sina Kalantarzadeh, Nathan Klein, and Victor Reis. A Randomized Rounding Approach for DAG Edge Deletion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kalantarzadeh_et_al:LIPIcs.APPROX/RANDOM.2025.18,
  author =	{Kalantarzadeh, Sina and Klein, Nathan and Reis, Victor},
  title =	{{A Randomized Rounding Approach for DAG Edge Deletion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.18},
  URN =		{urn:nbn:de:0030-drops-243840},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.18},
  annote =	{Keywords: Approximation Algorithms, Randomized Algorithms, Linear Programming, Graph Algorithms, Scheduling}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2020.62

Sensitivity Lower Bounds from Linear Dependencies

Authors: Sophie Laplante, Reza Naserasr, and Anupa Sunny

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H_n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by s₀(f) s₁(f), a strictly stronger statement which implies the sensitivity conjecture.

Cite as

Sophie Laplante, Reza Naserasr, and Anupa Sunny. Sensitivity Lower Bounds from Linear Dependencies. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.MFCS.2020.62,
  author =	{Laplante, Sophie and Naserasr, Reza and Sunny, Anupa},
  title =	{{Sensitivity Lower Bounds from Linear Dependencies}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.62},
  URN =		{urn:nbn:de:0030-drops-127320},
  doi =		{10.4230/LIPIcs.MFCS.2020.62},
  annote =	{Keywords: Boolean Functions, Polynomial Degree, Sensitivity}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2020

Refine by Author
1 Kalantarzadeh, Sina
1 Klein, Nathan
1 Laplante, Sophie
1 Naserasr, Reza
1 Reis, Victor
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
1 Mathematics of computing → Approximation algorithms
1 Theory of computation → Approximation algorithms analysis
1 Theory of computation → Computational complexity and cryptography

Refine by Keyword
1 Approximation Algorithms
1 Boolean Functions
1 Graph Algorithms
1 Linear Programming
1 Polynomial Degree
Show More...

2 Search Results for "Naserasr, Reza"

A Randomized Rounding Approach for DAG Edge Deletion

Abstract

Cite as

Sensitivity Lower Bounds from Linear Dependencies

Abstract

Cite as

Thanks for your feedback!

Could not send message