1 Search Results for "Seimi, Kento"

Document
DOI: 10.4230/LIPIcs.ISAAC.2016.42
Optimal Composition Ordering Problems for Piecewise Linear Functions

Authors: Yasushi Kawase, Kazuhisa Makino, and Kento Seimi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In this paper, we introduce maximum composition ordering problems. The input is n real functions f_1 , ... , f_n : R to R and a constant c in R. We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation sigma : [n] to [n] which maximizes f_{sigma(n)} circ f_{sigma(n-1)} circ ... circ f_{sigma(1)}(c), where [n] = {1, ... , n}. The maximum partial composition ordering problem is to compute a permutation sigma : [n] to [n] and a nonnegative integer k (0 le k le n) which maximize f_{sigma(k)} circ f_{sigma(k-1)} circ ... circ f_{sigma(1)}(c). We propose O(n log n) time algorithms for the maximum total and partial composition ordering problems for monotone linear functions f_i , which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum partial composition ordering problem can be solved in polynomial time if f i is of the form max{a_i x + b_i , c_i } for some constants a_i (ge 0), b_i and c_i. As a corollary, we show that the two-valued free-order secretary problem can be solved in polynomial time. We finally prove that there exists no constant-factor approximation algorithm for the problems, even if f_i's are monotone, piecewise linear functions with at most two pieces, unless P=NP.
Cite as

Yasushi Kawase, Kazuhisa Makino, and Kento Seimi. Optimal Composition Ordering Problems for Piecewise Linear Functions. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2016.42,
  author =	{Kawase, Yasushi and Makino, Kazuhisa and Seimi, Kento},
  title =	{{Optimal Composition Ordering Problems for Piecewise Linear Functions}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.42},
  URN =		{urn:nbn:de:0030-drops-68126},
  doi =		{10.4230/LIPIcs.ISAAC.2016.42},
  annote =	{Keywords: function composition, time-dependent scheduling}
}
  • Refine by Author
  • 1 Kawase, Yasushi
  • 1 Makino, Kazuhisa
  • 1 Seimi, Kento

  • Refine by Classification

  • Refine by Keyword
  • 1 function composition
  • 1 time-dependent scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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