Problems of order optimization

DOI10.1023/A:1012709400447MaRDI QIDQ5960195zbMATH OpenOpenAlexFDO

Authors N. A. Sokolov

Publication date 15 December 2002

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1012709400447

zbMATH Keywords

monotone Boolean functionsorder optimizationorder relationsShannon function

Mathematics Subject Classification ID

Partial orders, general (06A06) Boolean functions (06E30)

Review text

In the introduction, different results concerning the investigation of monotone Boolean functions are presented, and it is mentioned that the aim of this paper is a restatement of a class of combinatorial problems in terms of the order optimization on finite partially ordered sets. The main definitions and the statement of the studied problems are presented in Section 2. In Section 3 the problem of order optimization on the Boolean cube is presented. In the set of all extensions of the natural order relation, the inductive order relation \(\leq_i\), the layered inductive order relation \(\leq_s\) and the canonical order relation \(\leq_c\) are considered. For those relations the following order of inclusions holds: \(\leq\subset\leq_c\subset\leq_s\subset\leq_i\). In the theorems 1-5, the relations that hold for the Shannon function \(\varphi(n)\) of different problems concerning the monotone Boolean functions are given. In Section 4 the problem of order optimization of a finite-valued \(n\)-dimensional lattice is considered, and some relations concerning the Shannon function of different problems are proved. In Section 5 the canonical order \(M(n)\) is considered, and a relation that holds for the Shannon function of order optimization with an oracle on the lattice \(M(n)\) is proved. The distributive lattice generated by the set of all \(n\)-element sets ordered in nondecreasing order is considered in Section 6, and a relation for the Shannon function of the order optimization with an oracle is proved.

Recommendations

• Ordering of intervals and optimization problems with interval parameters
• scientific article; zbMATH DE number 894717
• Optimal ordered problem solver
• On discrete optimization with ordering
• scientific article; zbMATH DE number 2084756
• Order-constrained linear optimization
• Simple optimization problems via majorization ordering
• On the Greedy Solution of Ordering Problems
• On a setup optimization problem for interval orders
• On Solving Optimization Problems with Ordered Average Criteria and Constraints

Cited in

(9)

• On Solving Optimization Problems with Ordered Average Criteria and Constraints
• scientific article; zbMATH DE number 4181404 (Why is no real title available?)
• Partial decoding of monotonic Boolean functions
• Simple optimization problems via majorization ordering
• Solving simplification ordering constraints
• scientific article; zbMATH DE number 4193487 (Why is no real title available?)
• scientific article; zbMATH DE number 3312376 (Why is no real title available?)
• scientific article; zbMATH DE number 7701188 (Why is no real title available?)
• Optimal ordered problem solver

This page was built for publication: Problems of order optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5960195)