Academic literature on the topic 'Epsilon Net Problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Epsilon Net Problem.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Epsilon Net Problem"
1
Adekanmbi, Oluwole, Oludayo Olugbara, and Josiah Adeyemo. "An Investigation of Generalized Differential Evolution Metaheuristic for Multiobjective Optimal Crop-Mix Planning Decision." Scientific World Journal 2014 (2014): 1–8. http://dx.doi.org/10.1155/2014/258749.
Full textAbstract:
This paper presents an annual multiobjective crop-mix planning as a problem of concurrent maximization of net profit and maximization of crop production to determine an optimal cropping pattern. The optimal crop production in a particular planting season is a crucial decision making task from the perspectives of economic management and sustainable agriculture. A multiobjective optimal crop-mix problem is formulated and solved using the generalized differential evolution 3 (GDE3) metaheuristic to generate a globally optimal solution. The performance of the GDE3 metaheuristic is investigated by comparing its results with the results obtained using epsilon constrained and nondominated sorting genetic algorithms—being two representatives of state-of-the-art in evolutionary optimization. The performance metrics of additive epsilon, generational distance, inverted generational distance, and spacing are considered to establish the comparability. In addition, a graphical comparison with respect to the true Pareto front for the multiobjective optimal crop-mix planning problem is presented. Empirical results generally show GDE3 to be a viable alternative tool for solving a multiobjective optimal crop-mix planning problem.
2
Escobar, John Willmer, William Adolfo Hormaza Peña, and Rafael Guillermo García-Cáceres. "Robust multiobjective scheme for closed-loop supply chains by considering financial criteria and scenarios." International Journal of Industrial Engineering Computations 14, no. 2 (2023): 361–80. http://dx.doi.org/10.5267/j.ijiec.2022.12.004.
Full textAbstract:
This paper considers the closed-loop supply chain design problem by examining financial criteria and uncertainty in the parameters. A robust multiobjective optimization methodology is proposed by considering financial measures such as maximizing the net present value (NPV) and minimizing the financial risk (FR). The proposed methodology integrates various multiobjective optimization elements based on epsilon constraints and robustness measurements through the FePIA (named after the four steps of the procedure: Feature–Perturbation–Impact–Analysis) methodology. Similarly, an analysis of the parameter variability using scenarios was considered. The proposed method's efficiency was tested with real information from a multinational company operating in Colombia. The results show the effectiveness of the methodology in addressing real problems associated with supply chain design.
3
Inoue, Takao. "A Sound Interpretation of Leśniewski's Epsilon in Modal Logic KTB." Bulletin of the Section of Logic 50, no. 4 (November 9, 2021): 455–63. http://dx.doi.org/10.18778/0138-0680.2021.25.
Full textAbstract:
In this paper, we shall show that the following translation \(I^M\) from the propositional fragment \(\bf L_1\) of Leśniewski's ontology to modal logic \(\bf KTB\) is sound: for any formula \(\phi\) and \(\psi\) of \(\bf L_1\), it is defined as (M1) \(I^M(\phi \vee \psi) = I^M(\phi) \vee I^M(\psi)\), (M2) \(I^M(\neg \phi) = \neg I^M(\phi)\), (M3) \(I^M(\epsilon ab) = \Diamond p_a \supset p_a . \wedge . \Box p_a \supset \Box p_b .\wedge . \Diamond p_b \supset p_a\), where \(p_a\) and \(p_b\) are propositional variables corresponding to the name variables \(a\) and \(b\), respectively. In the last, we shall give some comments including some open problems and my conjectures.
4
Wang, Ke-Liang, and Fu-Qin Zhang. "Investigating the Spatial Heterogeneity and Correlation Network of Green Innovation Efficiency in China." Sustainability 13, no. 3 (January 21, 2021): 1104. http://dx.doi.org/10.3390/su13031104.
Full textAbstract:
With environmental problems becoming increasingly serious worldwide, scholars’ research views on innovation have begun to pay more attention to the technological value from an ecological perspective, instead of simply analyzing the importance of technological innovation from the perspective of economic value. Currently, improving green innovation efficiency (GIE) has been considered as a critical path to realizing economic transformation and green development. Based on the global Super-Epsilon-based measure (EBM) model, Moran index, vector autoregression (VAR) model, and block model, this study investigated the temporal and spatial characteristics of GIE in 30 provinces in China from 2009 to 2017, and analyzed the spatial heterogeneity and spatial correlation network characteristics. The results showed that in spatial terms, China’s GIE presented an extremely unbalanced development model. In provinces with a higher GIE, there was an overall improvement of GIE, but there was a lower impact in provinces with a lower GIE. The efficiency of China’s green innovation could be divided into four blocks. The first block was the main overflow, the second block was the broker, the third block was the bilateral spillover, and the fourth block was the net benefit. The four blocks had their own functions, and a very significant correlation was observed among them.
5
Naszódi, Márton, and Moritz Venzin. "Covering Convex Bodies and the Closest Vector Problem." Discrete & Computational Geometry, May 1, 2022. http://dx.doi.org/10.1007/s00454-022-00392-x.
Full textAbstract:
AbstractWe present algorithms for the $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of $$2^{O(n)}(1/\epsilon )^n$$ 2 O ( n ) ( 1 / ϵ ) n . We improve this substantially in the following two cases. First, for $$\ell _p$$ ℓ p -norms with $$p>2$$ p > 2 (resp. $$p \in [1,2]$$ p ∈ [ 1 , 2 ] ) fixed, we present an algorithm with a running time of $$2^{O(n)}(1+1/\epsilon )^{n/2}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / 2 (resp. $$2^{O(n)} (1+1/\epsilon )^{n/p}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / p ). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor 2 around their centroids, each one is contained in the $$(1+\epsilon )$$ ( 1 + ϵ ) -scaled homothet of the norm ball? We provide upper bounds for this $$(2,\epsilon )$$ ( 2 , ϵ ) -covering number by exploiting the modulus of smoothness of the $$\ell _p$$ ℓ p -balls. Applying a covering scheme, we can boost any 2-approximation algorithm for CVP to a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithm with the improved run time, either using a straightforward sampling routine or using the deterministic algorithm of Dadush for the construction of an epsilon net. Second, we consider polyhedral and zonotopal norms. For centrally symmetric polytopes (resp. zonotopes) in $${\mathbb R}^n$$ R n with O(n) facets (resp. generated by O(n) line segments), we provide a deterministic $$O(\log _2(2+1/\epsilon ))^{O(n)}$$ O ( log 2 ( 2 + 1 / ϵ ) ) O ( n ) time algorithm. This generalizes the result of Eisenbrand et al. which applies to the $$\ell _\infty $$ ℓ ∞ -norm. Finally, we establish a connection between the modulus of smoothness and lattice sparsification. As a consequence, using the enumeration and sparsification tools developped by Dadush, Kun, Peikert, and Vempala, we present a simple alternative to the boosting procedure with the same time and space requirement for $$\ell _p$$ ℓ p norms. This connection might be of independent interest.
6
Yi, Zhang. "nmODE: neural memory ordinary differential equation." Artificial Intelligence Review, May 22, 2023. http://dx.doi.org/10.1007/s10462-023-10496-2.
Full textAbstract:
AbstractBrain neural networks are regarded as dynamical systems in neural science, in which memories are interpreted as attractors of the systems. Mathematically, ordinary differential equations (ODEs) can be utilized to describe dynamical systems. Any ODE that is employed to describe the dynamics of a neural network can be called a neuralODE. Inspired by rethinking the nonlinear representation ability of existing artificial neural networks together with the functions of columns in the neocortex, this paper proposes a theory of memory-based neuralODE, which is composed of two novel artificial neural network models: nmODE and $$\epsilon$$ ϵ -net, and two learning algorithms: nmLA and $$\epsilon$$ ϵ -LA. The nmODE (neural memory Ordinary Differential Equation) is designed with a special structure that separates learning neurons from memory neurons, making its dynamics clear. Given any external input, the nmODE possesses the global attractor property and is thus embedded with a memory mechanism. The nmODE establishes a nonlinear mapping from the external input to its associated attractor and does not have the problem of learning features homeomorphic to the input data space, as occurs frequently in most existing neuralODEs. The nmLA (neural memory Learning Algorithm) is developed by proposing an interesting three-dimensional inverse ODE (invODE) and has advantages in memory and parameter efficiency. The proposed $$\epsilon$$ ϵ -net is a discrete version of the nmODE, which is particularly feasible for digital computing. The proposed $$\epsilon$$ ϵ -LA ($$\epsilon$$ ϵ learning algorithm) requires no prior knowledge of the number of network layers. Both nmLA and $$\epsilon$$ ϵ -LA have no problem with gradient vanishing. Experimental results show that the proposed theory is comparable to state-of-the-art methods.
7
Albiac, F., O. Blasco, and E. Briem. "On the norm-preservation of squares in real algebra representation." Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas 115, no. 4 (July 21, 2021). http://dx.doi.org/10.1007/s13398-021-01102-7.
Full textAbstract:
AbstractOne of the main results of the article Gelfand theory for real Banach algebras, recently published in [Rev R Acad Cienc Exactas Fís Nat Ser A Mat RACSAM 114(4):163, 2020] is Proposition 4.1, which establishes that the norm inequality $$\Vert a^{2}\Vert \le \Vert a^{2}+b^{2}\Vert $$ ‖ a 2 ‖ ≤ ‖ a 2 + b 2 ‖ for $$a,b\in {\mathcal {A}}$$ a , b ∈ A is sufficient for a commutative real Banach algebra $${\mathcal {A}}$$ A with a unit to be isomorphic to the space $${\mathcal {C}}_{{\mathbb {R}}}({\mathcal {K}})$$ C R ( K ) of continuous real-valued functions on a compact Hausdorff space $${\mathcal {K}}$$ K . Moreover, in this proposition is also shown that if the above condition (which involves all the operations of the algebra) holds, then the real-algebra isomorphism given by the Gelfand transform preserves the norm of squares. A very natural question springing from the above-mentioned result is whether an isomorphism of $${\mathcal {A}}$$ A onto $${\mathcal {C}}_{{\mathbb {R}}}({\mathcal {K}})$$ C R ( K ) is always norm-preserving of squares. This note is devoted to providing a negative answer to this problem. To that end, we construct algebra norms on spaces $${\mathcal {C}}_{{\mathbb {R}}}({\mathcal {K}})$$ C R ( K ) which are $$(1+\epsilon )$$ ( 1 + ϵ ) -equivalent to the sup-norm and with the norm of the identity function equal to 1, where the norm of every nonconstant function is different from the standard sup-norm. We also provide examples of two-dimensional normed real algebras $${\mathcal {A}}$$ A where $$\Vert a^2\Vert \le k \Vert a^2+b^2\Vert $$ ‖ a 2 ‖ ≤ k ‖ a 2 + b 2 ‖ for all $$a,b\in {\mathcal {A}}$$ a , b ∈ A , for some $$k>1$$ k > 1 , but the inequality fails for $$k=1$$ k = 1 .
Dissertations / Theses on the topic "Epsilon Net Problem"
1
Bharadwaj, Subramanya B. V. "Variants and Generalization of Some Classical Problems in Combinatorial Geometry." Thesis, 2014. http://etd.iisc.ac.in/handle/2005/3134.
Full textAbstract:
In this thesis we consider extensions and generalizations of some classical problems
in Combinatorial Geometry. Our work is an offshoot of four classical problems in
Combinatorial Geometry. A fundamental assumption in these problems is that the
underlying point set is R2. Two fundamental themes entwining the problems considered
in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since.
Avis et al. in 2001 posed the following question which we call the n-interior point
problem: Is there a finite integer g(n) for every n, such that, every point set P with
g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset
which is a convex polygon that contains exactly n interior points. They showed that
g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers.
We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily
C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed
the following fundamental question which can be considered as a generalised version of
Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known.
Inspired by the original question of Danzer and Gr¨unbaum we consider their question
in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting.
In the third part of this thesis, we broadly look at hitting and covering questions
with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively.
These problems has been well studied in the case when P = R2. We systematically
look at the case when P is finite, showing bounds for intervals, halfspaces, orthants,
unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2.
Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the
strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any
object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express
the bound on the size of the set Q in terms of ǫ.
Let G be a uniform √n × √n grid. It is an intriguing question as to whether we
get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.
2
Bharadwaj, Subramanya B. V. "Variants and Generalization of Some Classical Problems in Combinatorial Geometry." Thesis, 2014. http://hdl.handle.net/2005/3134.
Full textAbstract:
In this thesis we consider extensions and generalizations of some classical problems
in Combinatorial Geometry. Our work is an offshoot of four classical problems in
Combinatorial Geometry. A fundamental assumption in these problems is that the
underlying point set is R2. Two fundamental themes entwining the problems considered
in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since.
Avis et al. in 2001 posed the following question which we call the n-interior point
problem: Is there a finite integer g(n) for every n, such that, every point set P with
g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset
which is a convex polygon that contains exactly n interior points. They showed that
g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers.
We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily
C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed
the following fundamental question which can be considered as a generalised version of
Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known.
Inspired by the original question of Danzer and Gr¨unbaum we consider their question
in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting.
In the third part of this thesis, we broadly look at hitting and covering questions
with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively.
These problems has been well studied in the case when P = R2. We systematically
look at the case when P is finite, showing bounds for intervals, halfspaces, orthants,
unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2.
Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the
strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any
object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express
the bound on the size of the set Q in terms of ǫ.
Let G be a uniform √n × √n grid. It is an intriguing question as to whether we
get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.
Book chapters on the topic "Epsilon Net Problem"
1
Panahian, Saeed, and Zarita Zainuddin. "Theoretical Analyses of the Universal Approximation Capability of a class of Higher Order Neural Networks based on Approximate Identity." In Advances in Computational Intelligence and Robotics, 192–207. IGI Global, 2016. http://dx.doi.org/10.4018/978-1-5225-0063-6.ch008.
Full textAbstract:
One of the most important problems in the theory of approximation functions by means of neural networks is universal approximation capability of neural networks. In this study, we investigate the theoretical analyses of the universal approximation capability of a special class of three layer feedforward higher order neural networks based on the concept of approximate identity in the space of continuous multivariate functions. Moreover, we present theoretical analyses of the universal approximation capability of the networks in the spaces of Lebesgue integrable multivariate functions. The methods used in proving our results are based on the concepts of convolution and epsilon-net. The obtained results can be seen as an attempt towards the development of approximation theory by means of neural networks.
Conference papers on the topic "Epsilon Net Problem"
1
Shan, Liren, Yuhao Yi, and Zhongzhi Zhang. "Improving Information Centrality of a Node in Complex Networks by Adding Edges." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/491.
Full textAbstract:
The problem of increasing the centrality of a network node arises in many practical applications. In this paper, we study the optimization problem of maximizing the information centrality Iv of a given node v in a network with n nodes and m edges, by creating k new edges incident to v. Since Iv is the reciprocal of the sum of resistance distance Rv between v and all nodes, we alternatively consider the problem of minimizing Rv by adding k new edges linked to v. We show that the objective function is monotone and supermodular. We provide a simple greedy algorithm with an approximation factor (1 − 1/e) and O(n^3) running time. To speed up the computation, we also present an algorithm to compute (1 − 1/e − epsilon) approximate resistance distance Rv after iteratively adding k edges, the running time of which is Otilde(mk*epsilon^−2) for any epsilon > 0, where the Otilde(·) notation suppresses the poly(log n) factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms.
2
Gupta, Sushmita, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. "Winning a Tournament by Any Means Necessary." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/39.
Full textAbstract:
In a tournament, $n$ players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph $D$), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player $w$ wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when $\ell<(1-\epsilon)\log n$ alterations are possible (for any fixed $\epsilon>0$). For this problem, our contribution is fourfold. First, we present two operations that ``obfuscate deceit'': given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to $w$ and ``elite players''. Third, we give a closed formula for the case where $D$ is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.
3
Soos, Mate, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, and Maciej Obremski. "Engineering an Efficient Approximate DNF-Counter." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/226.
Full textAbstract:
Model counting is a fundamental problem with many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In this work, we focus on a variant of this problem where the underlying formula is expressed in Disjunctive Normal Form (DNF), also known as #DNF. This problem has been shown to be #P-complete, making it intractable to solve exactly. Much research has therefore been focused on obtaining approximate solutions, particularly in the form of (epsilon, delta) approximations. The primary contribution of this paper is a new approach, called pepin, to approximate #DNF counting that achieves (nearly) optimal time complexity and outperforms existing FPRAS. Our approach is based on the recent breakthrough in the context of union of sets in streaming. We demonstrate the effectiveness of our approach through extensive experiments and show that it provides an affirmative answer to the challenge of efficiently computing #DNF.
4
Chen, Jingwei, and Nathan R. Sturtevant. "Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/170.
Full textAbstract:
Many practical problems are too difficult to solve optimally, motivating the need to found suboptimal solutions, particularly those with bounds on the final solution quality. Algorithms like Weighted A*, A*-epsilon, Optimistic Search, EES, and DPS have been developed to find suboptimal solutions with solution quality that is within a constant bound of the optimal solution. However, with the exception of weighted A*, all of these algorithms require performing node re-expansions during search. This paper explores the properties of priority functions that can find bounded suboptimal solution without requiring node re-expansions. After general bounds are developed, two new convex priority functions are developed that can outperform weighted A*.
5
Walker, Thayne T., Nathan R. Sturtevant, and Ariel Felner. "Extended Increasing Cost Tree Search for Non-Unit Cost Domains." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/74.
Full textAbstract:
Multi-agent pathfinding (MAPF) has applications in navigation, robotics, games and planning. Most work on search-based optimal algorithms for MAPF has focused on simple domains with unit cost actions and unit time steps. Although these constraints keep many aspects of the algorithms simple, they also severely limit the domains that can be used. In this paper we introduce a new definition of the MAPF problem for non-unit cost and non-unit time step domains along with new multiagent state successor generation schemes for these domains. Finally, we define an extended version of the increasing cost tree search algorithm (ICTS) for non-unit costs, with two new sub-optimal variants of ICTS: epsilon-ICTS and w-ICTS. Our experiments show that higher quality sub-optimal solutions are achievable in domains with finely discretized movement models in no more time than lower-quality, optimal solutions in domains with coarsely discretized movement models.
6
Tartibu, L. K., and M. O. Okwu. "Optimization of a Manifold Microchannel Heat Sink Using an Improved Version of the Augmented Epsilon Constraint Method." In ASME 2019 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/imece2019-11496.
Full textAbstract:
Abstract The increase of heat generated in integrated circuit because of the miniaturization of electronic components requires more aggressive cooling solutions in order to minimize this high heat flux and address the temperature non-uniformity. In this paper, a manifold microchannel heat sinks has been investigated. In order to enhance the heat transfer performance of the microchannel, an improved version of the augmented epsilon constraint method is adopted for the optimization of the device. Four non-dimensional design variables have been used to describe the geometry of the manifold microchannel heat sinks. The thermal performance and the pumping power have been incorporated in the mathematical programming formulation as indicators of the thermal performance. A surrogate-based approximation based on the Response Surface Approximation has been utilized to evaluate these two objectives. This new mathematical approach has been implemented in the General Algebraic Modelling Systems (GAMS). Details about single and multi-objective optimization formulation of the problem will be disclosed. Optimal solutions describing the best geometrical configuration of the device will be computed. The implications of the geometrical configuration on the performance the manifold microchannel heat sinks will form part of the main contribution of this study.