3 Search Results for "Soma, Tasuku"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.41
On Maximizing Sums of Non-Monotone Submodular and Linear Functions

Authors: Benjamin Qi

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by [Bodek and Feldman '22]. In this problem, we are given query access to a non-negative submodular function f: 2^N → ℝ_{≥ 0} and a linear function 𝓁: 2^N → ℝ over the same ground set N, and the objective is to output a set T ⊆ N approximately maximizing the sum f(T)+𝓁(T). Specifically, an algorithm is said to provide an (α,β)-approximation for RegularizedUSM if it outputs a set T such that E[f(T)+𝓁(T)] ≥ max_{S ⊆ N}[α ⋅ f(S)+β⋅ 𝓁(S)]. We also study the setting where S and T are constrained to be independent in a given matroid, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM). The special case of RegularizedCSM with monotone f has been extensively studied [Sviridenko et al. '17, Feldman '18, Harshaw et al. '19]. On the other hand, we are aware of only one prior work that studies RegularizedCSM with non-monotone f [Lu et al. '21], and that work constrains 𝓁 to be non-positive. In this work, we provide improved (α,β)-approximation algorithms for both {RegularizedUSM} and {RegularizedCSM} with non-monotone f. In particular, we are the first to provide nontrivial (α,β)-approximations for RegularizedCSM where the sign of 𝓁 is unconstrained, and the α we obtain for RegularizedUSM improves over [Bodek and Feldman '22] for all β ∈ (0,1). In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the α our algorithm obtains for {RegularizedCSM} with unconstrained 𝓁 is essentially tight for β ≥ e/(e+1). Using similar ideas, we are also able to show 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to [Oveis Gharan and Vondrak '10].
Cite as

Benjamin Qi. On Maximizing Sums of Non-Monotone Submodular and Linear Functions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{qi:LIPIcs.ISAAC.2022.41,
  author =	{Qi, Benjamin},
  title =	{{On Maximizing Sums of Non-Monotone Submodular and Linear Functions}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.41},
  URN =		{urn:nbn:de:0030-drops-173263},
  doi =		{10.4230/LIPIcs.ISAAC.2022.41},
  annote =	{Keywords: submodular maximization, regularization, continuous greedy, inapproximability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.89
On Solving (Non)commutative Weighted Edmonds' Problem

Authors: Taihei Oki

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we consider computing the degree of the Dieudonné determinant of a polynomial matrix A = A_l + A_{l-1} s + ⋯ + A₀ s^l, where each A_d is a linear symbolic matrix, i.e., entries of A_d are affine functions in symbols x₁, …, x_m over a field K. This problem is a natural "weighted analog" of Edmonds' problem, which is to compute the rank of a linear symbolic matrix. Regarding x₁, …, x_m as commutative or noncommutative, two different versions of weighted and unweighted Edmonds' problems can be considered. Deterministic polynomial-time algorithms are unknown for commutative Edmonds' problem and have been proposed recently for noncommutative Edmonds' problem. The main contribution of this paper is to establish a deterministic polynomial-time reduction from (non)commutative weighted Edmonds' problem to unweighed Edmonds' problem. Our reduction makes use of the discrete Legendre conjugacy between the integer sequences of the maximum degree of minors of A and the rank of linear symbolic matrices obtained from the coefficient matrices of A. Combined with algorithms for noncommutative Edmonds' problem, our reduction yields the first deterministic polynomial-time algorithm for noncommutative weighted Edmonds' problem with polynomial bit-length bounds. We also give a reduction of the degree computation of quasideterminants and its application to the degree computation of noncommutative rational functions.
Cite as

Taihei Oki. On Solving (Non)commutative Weighted Edmonds' Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oki:LIPIcs.ICALP.2020.89,
  author =	{Oki, Taihei},
  title =	{{On Solving (Non)commutative Weighted Edmonds' Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.89},
  URN =		{urn:nbn:de:0030-drops-124963},
  doi =		{10.4230/LIPIcs.ICALP.2020.89},
  annote =	{Keywords: skew fields, Edmonds' problem, Dieudonn\'{e} determinant, degree computation, Smith - McMillan form, matrix expansion, discrete Legendre conjugacy}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.99
A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

Authors: Tasuku Soma and Yuichi Yoshida

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In monotone submodular function maximization, approximation guarantees based on the curvature of the objective function have been extensively studied in the literature. However, the notion of curvature is often pessimistic, and we rarely obtain improved approximation guarantees, even for very simple objective functions. In this paper, we provide a novel approximation guarantee by extracting an M^{natural}-concave function h:2^E -> R_+, a notion in discrete convex analysis, from the objective function f:2^E -> R_+. We introduce a novel notion called the M^{natural}-concave curvature of a given set function f, which measures how much f deviates from an M^{natural}-concave function, and show that we can obtain a (1-gamma/e-epsilon)-approximation to the problem of maximizing f under a cardinality constraint in polynomial time, where gamma is the value of the M^{natural}-concave curvature and epsilon > 0 is an arbitrary constant. Then, we show that we can obtain nontrivial approximation guarantees for various problems by applying the proposed algorithm.
Cite as

Tasuku Soma and Yuichi Yoshida. A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{soma_et_al:LIPIcs.ICALP.2018.99,
  author =	{Soma, Tasuku and Yoshida, Yuichi},
  title =	{{A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.99},
  URN =		{urn:nbn:de:0030-drops-91033},
  doi =		{10.4230/LIPIcs.ICALP.2018.99},
  annote =	{Keywords: Submodular Function, Approximation Algorithm, Discrete Convex Analysis}
}
  • Refine by Author
  • 1 Oki, Taihei
  • 1 Qi, Benjamin
  • 1 Soma, Tasuku
  • 1 Yoshida, Yuichi

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial optimization
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Computing methodologies → Linear algebra algorithms
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Approximation Algorithm
  • 1 Dieudonné determinant
  • 1 Discrete Convex Analysis
  • 1 Edmonds' problem
  • 1 Smith - McMillan form
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 1 2022

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