...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Optimal Composition Ordering Problems for Piecewise Linear Functions
【24h】

Optimal Composition Ordering Problems for Piecewise Linear Functions

机译：分段线性函数的最优组合排序问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we introduce maximum composition ordering problems. The input is n real functions $$f_1,dots ,f_n:mathbb {R}rightarrow mathbb {R}$$ f 1 , ⋯ , f n : R → R and a constant $$cin mathbb {R}$$ c ∈ R . We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation $$sigma :[n]rightarrow [n]$$ σ : [ n ] → [ n ] which maximizes $$f_{sigma (n)}circ f_{sigma (n-1)}circ dots circ f_{sigma (1)}(c)$$ f σ ( n ) ∘ f σ ( n - 1 ) ∘ ⋯ ∘ f σ ( 1 ) ( c ) , where $$[n]={1,dots ,n}$$ [ n ] = { 1 , ⋯ , n } . The maximum partial composition ordering problem is to compute a permutation $$sigma :[n]rightarrow [n]$$ σ : [ n ] → [ n ] and a nonnegative integer $$k~(0le kle n)$$ k ( 0 ≤ k ≤ n ) which maximize $$f_{sigma (k)}circ f_{sigma (k-1)}circ dots circ f_{sigma (1)}(c)$$ f σ ( k ) ∘ f σ ( k - 1 ) ∘ ⋯ ∘ f σ ( 1 ) ( c ) . We propose $$mathrm {O}(nlog n)$$ O ( n log n ) time algorithms for the maximum total and partial composition ordering problems for monotone linear functions $$f_i$$ f i , which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum total composition ordering problem can be solved in polynomial time if $$f_i$$ f i is of the form $$max {a_ix+b_i,d_i,x}$$ max { a i x + b i , d i , x } for some constants $$a_i,(ge 0)$$ a i ( ≥ 0 ) , $$b_i$$ b i and $$d_i$$ d 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$$ f i ’s are monotone, piecewise linear functions with at most two pieces, unless P  $$=$$ =  NP.
机译：在本文中，我们介绍了最大成分排序问题。输入是n个实函数$$ f_1，dots，f_n：mathbb {R} rightarrow mathbb {R} $$ f 1，⋯，fn：R→R和常数$$ cin mathbb {R} $$ c∈R 。我们考虑两种设置：全部和部分合成。最大总构图排序问题是计算一个置换$$ sigma：[n] rightarrow [n] $$σ：[n]→[n]，从而最大化$$ f_ {sigma（n）} circ f_ {sigma（n -1）}圈点circ f_ {sigma（1）}（c）$$ fσ（n）∘fσ（n-1）∘fσ（1）（c），其中$$ [n] = {1，dots，n} $$ [n] = {1，⋯，n}。最大局部合成排序问题是计算置换$$ sigma：[n] rightarrow [n] $$σ：[n]→[n]和非负整数$$ k〜（0le kle n）$$ k（ 0≤k≤n）最大化$$ f_ {sigma（k）}圈f_ {sigma（k-1）}圈点circ f_ {sigma（1）}（c）$$ fσ（k）∘fσ （k-1）∘fσ（1）（c）。针对单调线性函数$$ f_i $$ fi的最大总和部分成分排序问题，我们提出了$$ mathrm {O}（nlog n）$$ O（n log n）时间算法，该算法推广了线性退化和缩短模型时间相关的调度问题。我们还表明，如果$$ f_i $$ fi的形式为$$ max {a_ix + b_i，d_i，x} $$ max {aix + bi，di，x }对于某些常数$$ a_i，（ge 0）$$ ai（≥0），$ b_i $$ bi和$$ d_i $$ di。作为推论，我们证明了二值自由阶秘书问题可以在多项式时间内解决。我们最终证明，即使$$ f_i $$ f i是单调的分段线性函数，最多具有两个数，除非P = $$ = $ NP = NP，否则没有问题的恒定因数近似算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号