Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 27 for “"Cardinality constraint"”.
-
Solving Cardinality Constrained Quadratic Optimization Problems Using the Framework of Interval Branch and Bound
… number of available parameters, resulting in a cardinality-constraint ensuring that we only select a small number of parameters in the final optimal solution. These problems can be modeled as mixed integer optimization problems by introducing some binary variables to handle the …
-
Lagrangian Relaxation Approaches to Cardinality Constrained Portfolio Selection
Portfolio selection with cardinality constraint is a process that creates a strict subset of assets from a large selection pool. The advantage of cardinality constraint is that fewer assets can reduce transaction costs and complexity of asset management. Also, this type of constraint can be used to …
-
Cardinality Constrained Optimization Problems
… thesis, we examine optimization problems with a constraint that allows for only a certain number of variables to be nonzero. This constraint, which is called a cardinality constraint, has received considerable attention in a number of areas such as machine learning, statistics, computational …
-
Constrained submodular optimization and applications in information diffusion
… a submodular function with a submodular cost and cardinality constraint. We provide efficient approximation algorithms with data-dependent additive errors. We focus on an application in Information Diffusion by formulating the Constrained Influence Maximization Problem: the objective is to …
-
Optimization and separation for structured submodular functions with constraints
… as a substructure together with other side constraints. In Chapter 2, we develop approximation algorithms for the expected utility knapsack problem. We use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular …
-
New results on some quadratic programming problems
… contains two optimization problems with binary constraints. To solve these problems, we first explore some intrinsic relation between binary quadratic problem and data clustering. Then we utilize the explored relation to develop effective approximation algorithms. For example, the first problem …
-
Efficiency-based index tracking optimization model
We used asset efficiency constraints, measured by the Multifractal-Detrended Fluctuation Analysis (MF-DFA), in a classic index tracking model, obtaining a quadratic programming problem (QP). We form portfolios that seek to replicate the S&P500, Nikkei 225 and Ibovespa index, from the US, Japanese …
-
Scalable approximate algorithm for group influence maximization in online social network: An experimental evaluation
… is an instance of this optimization problem with cardinality constraint and δ-oracle. We develop a new scalable strategy for solving multiobjective problems where the objective functions closely represent influence maximization objectives and create a prototype implementation of our solution …
-
Optimal imputation of erroneous data
… charge problem and is closely related to the Cardinality Constraint Linear Programming problem (CCLP) the use of an extreme point enumeration algorithm such as one due Chernikova for solving MWFIC was suggested by Sande. Motivated by Rubin's adaptation of the Chernikova algorithm for solving …
-
Cardinality optimization problems
In this thesis, we discuss the cardinality minimization problem (CMP) and the cardinality constraint problem. Due to the NP-hardness of these problems, we discuss different computational and relaxation techniques for finding an approximate solution to these problems. We also discuss the …
-
Sparse Linear Discriminant Analysis with more Variables than Observations
… fourth methods achieve sparsity by imposing a cardinality constraint with the cardinality level determined by cross-validation. All the new methods reduce their computation time by sequentially determining individual discriminant functions. The methods are applied to six real data sets and …
-
Submodular optimization problems in the context of social influence
… {\em Multi-objective Optimization Problem with Cardinality Constraint in the context of $\delta$-approximate Oracles} and show that it is possible to ensure a $(1-1/e)^2 - 3\delta$ approximation guarantee. As the group influence maximization in online social networks is an instance of this …
-
Efficient Propagators for Global Constraints
We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The <em>global cardinality constraint</em> (GCC) ensures that a value <em>v</em> is assigned to at least <em>l<sub>v</sub></em> variables and to …
-
Generalizations, Extensions, and Applications of the Sequential Knapsack Problem
… by exploiting the divisibility property of the constraint. We then adapt this algorithm to provide an approximate solution for the more general Consecutive Bounded Sequential Knapsack Problem (CB-SKP). In this problem, items are partitioned into sets having divisible sizes, with the most general …
-
Parameterized Algorithms for Integer Linear Programs and Their Applications for Allocation Problems
… time approximation schemes (PTAS) for the Class Constraint Scheduling problems. Broadening our scope, we also investigate this problem and the closely related Cardinality Constraint Scheduling problem in the online setting and derive lower bounds for the approximation ratios as well as a PTAS for …
-
Towards Next Generation Sequential and Parallel SAT Solvers
… covered literal elimination and an advanced cardinality constraint extraction are introduced. By using these techniques, the reasoning of the overall SAT solving tool chain becomes stronger than plain resolution. When using these three techniques in the formula simplification tool Coprocessor …
-
Differentiable and Robust Optimization Algorithms
Imposing appropriate structure or constraints onto optimization problems is often the key to deriving guarantees or improving generalization of performance aspects like generalization or interpretability. The main contribution of this dissertation is developing algorithms that can leverage …
-
Logic programming and cardinality constraints : theory and practice
… sets. In this work we define an ASP language, cardinality constraint programs (CCP). The language extends normal logic programs by adding cardinality and conditional literals as well as choice rules. These extensions allow us to represent many if not most NP-complete problems in a concise and …
-
Advances on Portfolio Choices
… finding optimal mean-variance portfolios under a cardinality constraint. This problem is a mixed integer quadratic programming (MIQP) and is hard to solve. We propose a novel approach to reformulate the problem as a mixed integer linear programming (MILP) problem, which can be solved using any …
-
Arithmetic Combinations of Submodular and Supermodular Optimization and Submodular Generalized Matching for Peptide Identification in Tandem Mass Spectrometry
… such as submodular minimization without constraints or submodular maximization under a cardinality constraint. However, in real-world applications, the objective function is usually not a simple submodular function (or supermodular function) but is naturally written as an arithmetic …
Page 1 of 2