Search Results

Documents authored by Sviridenko, Maxim

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.3
Submodular Optimization with Contention Resolution Extensions

Authors: Benjamin Moseley and Maxim Sviridenko

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

Abstract
This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractional solution to the multi-linear extension and (2) rounding this solution to an integral solution via a contention resolution scheme. This line of research has improved results by either optimizing (1) or (2). Diverging from previous work, this paper introduces a principled method called contention resolution extensions of submodular functions. A contention resolution extension combines the contention resolution scheme into a continuous extension of a discrete submodular function. The contention resolution extension can be defined from effectively any contention resolution scheme. In the case where there is a loss in both (1) and (2), by optimizing them together, the losses can be combined resulting in an overall improvement. This paper showcases the concept by demonstrating that for the problem of optimizing a non-monotone submodular subject to the elements forming an independent set in an interval graph, the algorithm gives a .188-approximation. This improves upon the best known 1/(2e)~eq .1839 approximation.
Cite as

Benjamin Moseley and Maxim Sviridenko. Submodular Optimization with Contention Resolution Extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{moseley_et_al:LIPIcs.APPROX-RANDOM.2019.3,
  author =	{Moseley, Benjamin and Sviridenko, Maxim},
  title =	{{Submodular Optimization with Contention Resolution Extensions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-112188},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.3},
  annote =	{Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.19
Greedy Minimization of Weakly Supermodular Set Functions

Authors: Edo Liberty and Maxim Sviridenko

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

Abstract
Many problems in data mining and unsupervised machine learning take the form of minimizing a set function with cardinality constraints. More explicitly, denote by [n] the set {1,...,n} and let f(S) be a function from 2^[n] to R+. Our goal is to minimize f(S) subject to |S| <= k. These problems include clustering and covering problems as well as sparse regression, matrix approximation problems and many others. These combinatorial problems are hard to minimize in general. Finding good (e.g. constant factor) approximate solutions for them requires significant sophistication and highly specialized algorithms. In this paper we analyze the behavior of the greedy algorithm to all of these problems. We start by claiming that the functions above are special. A trivial observation is that they are non-negative and non-increasing, that is, f(S) >= f(union(S,T)) >= 0 for any S and T. This immediately shows that expanding solution sets is (at least potentially) beneficial in terms of reducing the function value. But, monotonicity is not sufficient to ensure that any number of greedy extensions of a given solution would significantly reduce the objective function.
Cite as

Edo Liberty and Maxim Sviridenko. Greedy Minimization of Weakly Supermodular Set Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{liberty_et_al:LIPIcs.APPROX-RANDOM.2017.19,
  author =	{Liberty, Edo and Sviridenko, Maxim},
  title =	{{Greedy Minimization of Weakly Supermodular Set Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{19:1--19:11},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.19},
  URN =		{urn:nbn:de:0030-drops-75682},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.19},
  annote =	{Keywords: Weak Supermodularity, Greedy Algorithms, Machine Learning, Data Mining}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.14
A Bi-Criteria Approximation Algorithm for k-Means

Authors: Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward

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

Abstract
We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee alpha(beta) depending on the number beta*k of clusters that may be opened. Our guarantee alpha(beta) is always at most 9 + epsilon and improves rapidly with beta (for example: alpha(2) < 2.59, and alpha(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.
Cite as

Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward. A Bi-Criteria Approximation Algorithm for k-Means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{makarychev_et_al:LIPIcs.APPROX-RANDOM.2016.14,
  author =	{Makarychev, Konstantin and Makarychev, Yury and Sviridenko, Maxim and Ward, Justin},
  title =	{{A Bi-Criteria Approximation Algorithm for k-Means}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.14},
  URN =		{urn:nbn:de:0030-drops-66370},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.14},
  annote =	{Keywords: k-means clustering, bicriteria approximation algorithms, linear programming, local search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.29
Submodular Stochastic Probing on Matroids

Authors: Marek Adamczyk, Maxim Sviridenko, and Justin Ward

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.
Cite as

Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 29-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.STACS.2014.29,
  author =	{Adamczyk, Marek and Sviridenko, Maxim and Ward, Justin},
  title =	{{Submodular Stochastic Probing on Matroids}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{29--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.29},
  URN =		{urn:nbn:de:0030-drops-44445},
  doi =		{10.4230/LIPIcs.STACS.2014.29},
  annote =	{Keywords: approximation algorithms, stochastic optimization, submodular optimization, matroids, iterative rounding}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.639
Stochastic Scheduling on Unrelated Machines

Authors: Martin Skutella, Maxim Sviridenko, and Marc Uetz

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the sizes of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. Here, the processing time of job j on machine i is governed by random variable P_{ij} , and its realization becomes known only upon job completion. With w_j being the given weight of job j, we study the objective to minimize the expected total weighted completion time E[Sum w_j.C_j] , where C_j is the completion time of job j. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+D)/2+e. Here, e>0 is arbitrarily small, and D is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates r_{ij}, our bound is (2+D)+e. We also show that the dependence of the performance guarantees on D is tight. Via D=0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.
Cite as

Martin Skutella, Maxim Sviridenko, and Marc Uetz. Stochastic Scheduling on Unrelated Machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 639-650, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{skutella_et_al:LIPIcs.STACS.2014.639,
  author =	{Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
  title =	{{Stochastic Scheduling on Unrelated Machines}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{639--650},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.639},
  URN =		{urn:nbn:de:0030-drops-44946},
  doi =		{10.4230/LIPIcs.STACS.2014.639},
  annote =	{Keywords: Stochastic Scheduling, Unrelated Machines, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.449
Energy Efficient Scheduling and Routing via Randomized Rounding

Authors: Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli, and Maxim Sviridenko

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed-scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
Cite as

Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli, and Maxim Sviridenko. Energy Efficient Scheduling and Routing via Randomized Rounding. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 449-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.FSTTCS.2013.449,
  author =	{Bampis, Evripidis and Kononov, Alexander and Letsios, Dimitrios and Lucarelli, Giorgio and Sviridenko, Maxim},
  title =	{{Energy Efficient Scheduling and Routing via Randomized Rounding}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{449--460},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.449},
  URN =		{urn:nbn:de:0030-drops-43923},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.449},
  annote =	{Keywords: Randomized rounding; scheduling; approximation; energy-aware; configuration linear program}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.465
Preemptive and Non-Preemptive Generalized Min Sum Set Cover

Authors: Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the ordering such that the first j elements in the ordering contain k(S_i) elements in S_i. This problem was introduced by [Azar, Gamzu and Yin, 2009] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when k(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem.
Cite as

Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan. Preemptive and Non-Preemptive Generalized Min Sum Set Cover. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{im_et_al:LIPIcs.STACS.2012.465,
  author =	{Im, Sungjin and Sviridenko, Maxim and van der Zwaan, Ruben},
  title =	{{Preemptive and Non-Preemptive Generalized Min Sum Set Cover}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{465--476},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.465},
  URN =		{urn:nbn:de:0030-drops-33991},
  doi =		{10.4230/LIPIcs.STACS.2012.465},
  annote =	{Keywords: Set Cover, Approximation, Preemption, Latency, Average cover time}
}
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 About DROPS Imprint Privacy Contact