5 Search Results for "Stanković, Aleksa"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.13
Max-Cut with Multiple Cardinality Constraints

Authors: Yury Makarychev, Madhusudhan Reddy Pittu, and Ali Vakilian

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

Abstract
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph G = (V, E), a partition of the vertices into c disjoint parts V₁, …, V_c, and cardinality parameters k₁, …, k_c, the goal is to select a set S ⊆ V such that |S ∩ V_i| = k_i for each i ∈ [c], maximizing the total weight of edges crossing S (i.e., edges with exactly one endpoint in S). By designing an approximate kernel for Constrained Max-Cut and building on the correlation rounding technique of Raghavendra and Tan (2012), we present a (0.858 - ε)-approximation algorithm for the problem when c = O(1). The algorithm runs in time O(min{k/ε, n}^poly(c/ε) + poly(n)), where k = ∑_{i∈[c]} k_i and n = |V|. This improves upon the (1/2 + ε₀)-approximation of Feige and Langberg (2001) for Max-Cut_k (the special case when c = 1, k₁ = k), and generalizes the (0.858 - ε)-approximation of Raghavendra and Tan (2012), which only applies when min{k,n-k} = Ω(n) and does not handle multiple constraints. We also establish that, for general values of c, it is NP-hard to determine whether a feasible solution exists that cuts all edges. Finally, we present a 1/2-approximation algorithm for Max-Cut under an arbitrary matroid constraint.
Cite as

Yury Makarychev, Madhusudhan Reddy Pittu, and Ali Vakilian. Max-Cut with Multiple Cardinality Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{makarychev_et_al:LIPIcs.APPROX/RANDOM.2025.13,
  author =	{Makarychev, Yury and Pittu, Madhusudhan Reddy and Vakilian, Ali},
  title =	{{Max-Cut with Multiple Cardinality Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{13:1--13:21},
  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.13},
  URN =		{urn:nbn:de:0030-drops-243790},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.13},
  annote =	{Keywords: Maxcut, Semi-definite Programming, Sum of Squares Hierarchy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.38
Optimal Inapproximability of Promise Equations over Finite Groups

Authors: Silvia Butti, Alberto Larrauri, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A celebrated result of Håstad established that, for any constant ε > 0, it is NP-hard to find an assignment satisfying a (1/|G|+ε)-fraction of the constraints of a given 3-LIN instance over an Abelian group G even if one is promised that an assignment satisfying a (1-ε)-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.
Cite as

Silvia Butti, Alberto Larrauri, and Stanislav Živný. Optimal Inapproximability of Promise Equations over Finite Groups. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.ICALP.2025.38,
  author =	{Butti, Silvia and Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Optimal Inapproximability of Promise Equations over Finite Groups}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.38},
  URN =		{urn:nbn:de:0030-drops-234150},
  doi =		{10.4230/LIPIcs.ICALP.2025.38},
  annote =	{Keywords: promise constraint satisfaction, approximation, linear equations}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.50
Some Results on Approximability of Minimum Sum Vertex Cover

Authors: Aleksa Stanković

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

Abstract
We study the Minimum Sum Vertex Cover problem, which asks for an ordering of vertices in a graph that minimizes the total cover time of edges. In particular, n vertices of the graph are visited according to an ordering, and for each edge this induces the first time it is covered. The goal of the problem is to find the ordering which minimizes the sum of the cover times over all edges in the graph. In this work we give the first explicit hardness of approximation result for Minimum Sum Vertex Cover. In particular, assuming the Unique Games Conjecture, we show that the Minimum Sum Vertex Cover problem cannot be approximated within 1.014. The best approximation ratio for Minimum Sum Vertex Cover as of now is 16/9, due to a recent work of Bansal, Batra, Farhadi, and Tetali. We also revisit an approximation algorithm for regular graphs outlined in the work of Feige, Lovász, and Tetali, and show that Minimum Sum Vertex Cover can be approximated within 1.225 on regular graphs.
Cite as

Aleksa Stanković. Some Results on Approximability of Minimum Sum Vertex Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{stankovic:LIPIcs.APPROX/RANDOM.2022.50,
  author =	{Stankovi\'{c}, Aleksa},
  title =	{{Some Results on Approximability of Minimum Sum Vertex Cover}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{50:1--50:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.50},
  URN =		{urn:nbn:de:0030-drops-171722},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.50},
  annote =	{Keywords: Hardness of approximation, approximability, approximation algorithms, Label Cover, Unique Games Conjecture, Vertex Cover}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.21
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs

Authors: Amey Bhangale and Aleksa Stanković

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely defined by its factor graph and the list of predicates. We show inapproximability of Max-3-LIN over non-abelian groups (both in the perfect completeness case and in the imperfect completeness case), with the same inapproximability factor as in the general case, even when the factor graph is fixed. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x⋅ y⋅ z = g, where x,y,z are the variables and g is a group element. We use representation theory and Fourier analysis over non-abelian groups to analyze the reductions.
Cite as

Amey Bhangale and Aleksa Stanković. Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.21,
  author =	{Bhangale, Amey and Stankovi\'{c}, Aleksa},
  title =	{{Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.21},
  URN =		{urn:nbn:de:0030-drops-156177},
  doi =		{10.4230/LIPIcs.ITCS.2022.21},
  annote =	{Keywords: Universal factor graphs, linear equations, non-abelian groups, hardness of approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.24
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

Authors: Per Austrin and Aleksa Stanković

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

Abstract
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within ~~0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within ~~0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (~~0.878 for Max-Cut, and ~~0.940 for Max-2-Sat). The hardness for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem.
Cite as

Per Austrin and Aleksa Stanković. Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.APPROX-RANDOM.2019.24,
  author =	{Austrin, Per and Stankovi\'{c}, Aleksa},
  title =	{{Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.24},
  URN =		{urn:nbn:de:0030-drops-112394},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.24},
  annote =	{Keywords: Constraint satisfaction problems, global cardinality constraints, semidefinite programming, inapproximability, Unique Games Conjecture, Max-Cut, Max-2-Sat}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2022
  • 1 2019

  • Refine by Author
  • 3 Stanković, Aleksa
  • 1 Austrin, Per
  • 1 Bhangale, Amey
  • 1 Butti, Silvia
  • 1 Larrauri, Alberto
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Problems, reductions and completeness
  • 2 Mathematics of computing → Approximation algorithms
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 Unique Games Conjecture
  • 2 linear equations
  • 1 Constraint satisfaction problems
  • 1 Hardness of approximation
  • 1 Label Cover
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact