Search Results

Documents authored by Schwartz, Roy

Document
DOI: 10.4230/LIPIcs.ESA.2023.52
A Tight Competitive Ratio for Online Submodular Welfare Maximization

Authors: Amit Ganz, Pranav Nuti, and Roy Schwartz

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

Abstract
In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given n bidders each equipped with a general non-negative (not necessarily monotone) submodular utility and m items that arrive online. The goal is to assign each item, once it arrives, to a bidder or discard it, while maximizing the sum of utilities. When an adversary determines the items' arrival order we present a simple randomized algorithm that achieves a tight competitive ratio of 1/4. The algorithm is a specialization of an algorithm due to [Harshaw-Kazemi-Feldman-Karbasi MOR`22], who presented the previously best known competitive ratio of 3-2√2≈ 0.171573 to the problem. When the items' arrival order is uniformly random, we present a competitive ratio of ≈ 0.27493, improving the previously known 1/4 guarantee. Our approach for the latter result is based on a better analysis of the (offline) Residual Random Greedy (RRG) algorithm of [Buchbinder-Feldman-Naor-Schwartz SODA`14], which we believe might be of independent interest.
Cite as

Amit Ganz, Pranav Nuti, and Roy Schwartz. A Tight Competitive Ratio for Online Submodular Welfare Maximization. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ganz_et_al:LIPIcs.ESA.2023.52,
  author =	{Ganz, Amit and Nuti, Pranav and Schwartz, Roy},
  title =	{{A Tight Competitive Ratio for Online Submodular Welfare Maximization}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{52:1--52: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.52},
  URN =		{urn:nbn:de:0030-drops-187052},
  doi =		{10.4230/LIPIcs.ESA.2023.52},
  annote =	{Keywords: Online Algorithms, Submodular Maximization, Welfare Maximization, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.69
An Improved Approximation Algorithm for the Max-3-Section Problem

Authors: Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh

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

Abstract
We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.
Cite as

Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh. An Improved Approximation Algorithm for the Max-3-Section Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.ESA.2023.69,
  author =	{Katzelnick, Dor and Pillai, Aditya and Schwartz, Roy and Singh, Mohit},
  title =	{{An Improved Approximation Algorithm for the Max-3-Section Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{69:1--69: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.69},
  URN =		{urn:nbn:de:0030-drops-187229},
  doi =		{10.4230/LIPIcs.ESA.2023.69},
  annote =	{Keywords: Approximation Algorithms, Semidefinite Programming, Max-Cut, Max-Bisection}
}
Document
DOI: 10.4230/DagRep.12.6.14
Efficient and Equitable Natural Language Processing in the Age of Deep Learning (Dagstuhl Seminar 22232)

Authors: Jesse Dodge, Iryna Gurevych, Roy Schwartz, Emma Strubell, and Betty van Aken

Published in: Dagstuhl Reports, Volume 12, Issue 6 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22232 "Efficient and Equitable Natural Language Processing in the Age of Deep Learning". Since 2012, the field of artificial intelligence (AI) has reported remarkable progress on a broad range of capabilities including object recognition, game playing, speech recognition, and machine translation. Much of this progress has been achieved by increasingly large and computationally intensive deep learning models: training costs for state-of-the-art deep learning models have increased 300,000 times between 2012 and 2018 [1]. Perhaps the epitome of this trend is the subfield of natural language processing (NLP) that over the past three years has experienced even sharper growth in model size and corresponding computational requirements in the word embedding approaches (e.g. ELMo, BERT, openGPT-2, Megatron-LM, T5, and GPT-3, one of the largest models ever trained with 175B dense parameters) that are now the basic building blocks of nearly all NLP models. Recent studies indicate that this trend is both environmentally unfriendly and prohibitively expensive, raising barriers to participation in NLP research [2,3]. The goal of this seminar was to mitigate these concerns and promote equity of access in NLP. References. [1] D. Amodei and D. Hernandez. 2018. AI and Compute. https://openai.com/blog/ai-and-compute [2] R. Schwartz, D. Dodge, N. A. Smith, and O. Etzioni. 2020. Green AI. Communications of the ACM (CACM) [3] E. Strubell, A. Ganesh, and A. McCallum. 2019. Energy and Policy Considerations for Deep Learning in NLP. In Proc. of ACL.
Cite as

Jesse Dodge, Iryna Gurevych, Roy Schwartz, Emma Strubell, and Betty van Aken. Efficient and Equitable Natural Language Processing in the Age of Deep Learning (Dagstuhl Seminar 22232). In Dagstuhl Reports, Volume 12, Issue 6, pp. 14-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{dodge_et_al:DagRep.12.6.14,
  author =	{Dodge, Jesse and Gurevych, Iryna and Schwartz, Roy and Strubell, Emma and van Aken, Betty},
  title =	{{Efficient and Equitable Natural Language Processing in the Age of Deep Learning (Dagstuhl Seminar 22232)}},
  pages =	{14--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{6},
  editor =	{Dodge, Jesse and Gurevych, Iryna and Schwartz, Roy and Strubell, Emma and van Aken, Betty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.6.14},
  URN =		{urn:nbn:de:0030-drops-174549},
  doi =		{10.4230/DagRep.12.6.14},
  annote =	{Keywords: deep learning, efficiency, equity, natural language processing (nlp)}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.37
Fair Correlation Clustering in General Graphs

Authors: Roy Schwartz and Roded Zats

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

Abstract
We consider the family of Correlation Clustering optimization problems under fairness constraints. In Correlation Clustering we are given a graph whose every edge is labeled either with a + or a -, and the goal is to find a clustering that agrees the most with the labels: + edges within clusters and - edges across clusters. The notion of fairness implies that there is no over, or under, representation of vertices in the clustering: every vertex has a color and the distribution of colors within each cluster is required to be the same as the distribution of colors in the input graph. Previously, approximation algorithms were known only for fair disagreement minimization in complete unweighted graphs. We prove the following: (1) there is no finite approximation for fair disagreement minimization in general graphs unless P = NP (this hardness holds also for bicriteria algorithms); and (2) fair agreement maximization in general graphs admits a bicriteria approximation of ≈ 0.591 (an improved ≈ 0.609 true approximation is given for the special case of two uniformly distributed colors). Our algorithm is based on proving that the sticky Brownian motion rounding of [Abbasi Zadeh-Bansal-Guruganesh-Nikolov-Schwartz-Singh SODA'20] copes well with uncut edges.
Cite as

Roy Schwartz and Roded Zats. Fair Correlation Clustering in General Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.APPROX/RANDOM.2022.37,
  author =	{Schwartz, Roy and Zats, Roded},
  title =	{{Fair Correlation Clustering in General Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{37:1--37:19},
  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.37},
  URN =		{urn:nbn:de:0030-drops-171591},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.37},
  annote =	{Keywords: Correlation Clustering, Approximation Algorithms, Semi-Definite Programming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.46
Fault Tolerant Max-Cut

Authors: Keren Censor-Hillel, Noa Marelly, Roy Schwartz, and Tigran Tonoyan

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

Abstract
In this work, we initiate the study of fault tolerant Max-Cut, where given an edge-weighted undirected graph G = (V,E), the goal is to find a cut S ⊆ V that maximizes the total weight of edges that cross S even after an adversary removes k vertices from G. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures k we present an approximation of (0.878-ε) against an adaptive adversary and of α_{GW}≈ 0.8786 against an oblivious adversary (here α_{GW} is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of α_{GW} against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max-Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.
Cite as

Keren Censor-Hillel, Noa Marelly, Roy Schwartz, and Tigran Tonoyan. Fault Tolerant Max-Cut. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2021.46,
  author =	{Censor-Hillel, Keren and Marelly, Noa and Schwartz, Roy and Tonoyan, Tigran},
  title =	{{Fault Tolerant Max-Cut}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{46:1--46: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.46},
  URN =		{urn:nbn:de:0030-drops-141158},
  doi =		{10.4230/LIPIcs.ICALP.2021.46},
  annote =	{Keywords: fault-tolerance, max-cut, approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.49
Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains

Authors: Dor Katzelnick and Roy Schwartz

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

Abstract
Correlation Clustering is an elegant model where given a graph with edges labeled + or -, the goal is to produce a clustering that agrees the most with the labels: + edges should reside within clusters and - edges should cross between clusters. In this work we study the MaxCorr objective, aiming to find a clustering that maximizes the difference between edges classified correctly and incorrectly. We focus on the case of bipartite graphs and present an improved approximation of 0.254, improving upon the known approximation of 0.219 given by Charikar and Wirth [FOCS`2004] and going beyond the 0.2296 barrier imposed by their technique. Our algorithm is inspired by Krivine’s method for bounding Grothendieck’s constant, and we extend this method to allow for more than two clusters in the output. Moreover, our algorithm leads to two additional results: (1) the first known approximation guarantees for MaxCorr where the output is constrained to have a bounded number of clusters; and (2) a natural extension of Grothendieck’s inequality to large domains.
Cite as

Dor Katzelnick and Roy Schwartz. Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.APPROX/RANDOM.2020.49,
  author =	{Katzelnick, Dor and Schwartz, Roy},
  title =	{{Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{49:1--49:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  URN =		{urn:nbn:de:0030-drops-126525},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  annote =	{Keywords: Correlation Clustering, Grothendieck’s Inequality, Approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.53
Approximating Requirement Cut via a Configuration LP

Authors: Roy Schwartz and Yotam Sharoni

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

Abstract
We consider the {Requirement Cut} problem, where given an undirected graph G = (V,E) equipped with non-negative edge weights c:E → R_{+}, and g groups of vertices X₁,…,X_{g} ⊆ V each equipped with a requirement r_i, the goal is to find a collection of edges F ⊆ E, with total minimum weight, such that once F is removed from G in the resulting graph every X_{i} is broken into at least r_{i} connected components. {Requirement Cut} captures multiple classic cut problems in graphs, e.g., {Multicut}, {Multiway Cut}, {Min k-Cut}, {Steiner k-Cut}, {Steiner Multicut}, and {Multi-Multiway Cut}. Nagarajan and Ravi [Algoritmica`10] presented an approximation of O(log{n}log{R}) for the problem, which was subsequently improved to O(log{g} log{k}) by Gupta, Nagarajan and Ravi [Operations Research Letters`10] (here R = ∑ _{i = 1}^g r_i and k = |∪ _{i = 1}^g X_i |). We present an approximation of O(Xlog{R} √{log{k}}log{log{k}}) for {Requirement Cut} (here X = max _{i = 1,…,g} {|X_i|}). Our approximation in general is incomparable to the above mentioned previous results, however when all groups are not too large, i.e., X = o((√{log{k}}log{g})/(log{R}log{log{k}})), it is better. Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.
Cite as

Roy Schwartz and Yotam Sharoni. Approximating Requirement Cut via a Configuration LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.APPROX/RANDOM.2020.53,
  author =	{Schwartz, Roy and Sharoni, Yotam},
  title =	{{Approximating Requirement Cut via a Configuration LP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{53:1--53:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.53},
  URN =		{urn:nbn:de:0030-drops-126560},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.53},
  annote =	{Keywords: Approximation, Requirement Cut, Sparsest Cut, Metric Embedding}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.27
Online and Offline Algorithms for Circuit Switch Scheduling

Authors: Roy Schwartz, Mohit Singh, and Sina Yazdanbod

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay delta is incurred during which no data can be transmitted. For the offline version of the problem we present a (1-(1/e)-epsilon) approximation ratio (for any constant epsilon >0). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.
Cite as

Roy Schwartz, Mohit Singh, and Sina Yazdanbod. Online and Offline Algorithms for Circuit Switch Scheduling. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.FSTTCS.2019.27,
  author =	{Schwartz, Roy and Singh, Mohit and Yazdanbod, Sina},
  title =	{{Online and Offline Algorithms for Circuit Switch Scheduling}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.27},
  URN =		{urn:nbn:de:0030-drops-115893},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.27},
  annote =	{Keywords: approximation algorithm, online, matching, scheduling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.82
Graph Balancing with Orientation Costs

Authors: Roy Schwartz and Ran Yeheskel

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: given an undirected multi-graph G=(V,E) equipped with edge weights and orientation costs on the edges, the goal is to find an orientation of the edges that minimizes both the maximum weight of edges oriented toward any vertex (makespan) and total orientation cost. We present a general framework for minimizing makespan in the presence of costs that allows us to: (1) achieve bicriteria approximations for the Graph Balancing problem that capture known previous results (Shmoys-Tardos [Math. Progrm. '93], Ebenlendr-Krcál-Sgall [Algorithmica '14], and Wang-Sitters [Inf. Process. Lett. '16]); and (2) achieve bicriteria approximations for extensions of the Graph Balancing problem that admit hyperedges and unrelated weights. Our framework is based on a remarkably simple rounding of a strengthened linear relaxation. We complement the above by presenting bicriteria lower bounds with respect to the linear programming relaxations we use that show that a loss in the total orientation cost is required if one aims for an approximation better than 2 in the makespan.
Cite as

Roy Schwartz and Ran Yeheskel. Graph Balancing with Orientation Costs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.ESA.2019.82,
  author =	{Schwartz, Roy and Yeheskel, Ran},
  title =	{{Graph Balancing with Orientation Costs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.82},
  URN =		{urn:nbn:de:0030-drops-112034},
  doi =		{10.4230/LIPIcs.ESA.2019.82},
  annote =	{Keywords: Graph Balancing, Generalized Assignment Problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.85
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

Authors: Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant epsilon >0 achieves a guarantee of 1-(1/e)-epsilon while violating only the covering constraints by a multiplicative factor of 1-epsilon. Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraint as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach. While this approach does not give tight bounds it yields deterministic and in some special cases also considerably faster algorithms. For example, for the well-studied special case of only packing constraints (Kulik et al. [Math. Oper. Res. `13] and Chekuri et al. [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.
Cite as

Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal. A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mizrachi_et_al:LIPIcs.ICALP.2019.85,
  author =	{Mizrachi, Eyal and Schwartz, Roy and Spoerhase, Joachim and Uniyal, Sumedha},
  title =	{{A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{85:1--85:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.85},
  URN =		{urn:nbn:de:0030-drops-106610},
  doi =		{10.4230/LIPIcs.ICALP.2019.85},
  annote =	{Keywords: submodular function, approximation algorithm, covering, packing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.34
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

Authors: Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Roy Schwartz

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.
Cite as

Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Roy Schwartz. Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2017.34,
  author =	{Chen, Shahar and Di Castro, Dotan and Karnin, Zohar and Lewin-Eytan, Liane and Naor, Joseph (Seffi) and Schwartz, Roy},
  title =	{{Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.34},
  URN =		{urn:nbn:de:0030-drops-74612},
  doi =		{10.4230/LIPIcs.ICALP.2017.34},
  annote =	{Keywords: approximation algorithms, randomized rounding, dependent rounding, metric labeling, classification}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.258
Discrepancy Without Partial Colorings

Authors: Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh

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

Abstract
Spencer's theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be "colored" by the values +1 or -1 such that the sum of every set is O(sqrt(n)) in absolute value. All existing proofs of this result recursively construct "partial colorings", which assign +1 or -1 values to half of the ground set. We devise the first algorithm for Spencer's theorem that directly computes a coloring, without recursively computing partial colorings.
Cite as

Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. Discrepancy Without Partial Colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 258-273, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{harvey_et_al:LIPIcs.APPROX-RANDOM.2014.258,
  author =	{Harvey, Nicholas J. A. and Schwartz, Roy and Singh, Mohit},
  title =	{{Discrepancy Without Partial Colorings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{258--273},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.258},
  URN =		{urn:nbn:de:0030-drops-47014},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.258},
  annote =	{Keywords: Combinatorial Discrepancy, Brownian Motion, Semi-Definite Programming, Randomized Algorithm}
}
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