Name
Title | ||
|---|---|---|
Exact and approximate discrete optimization algorithms for finding useful disjunctions of categorical predicates in data analysis |
Abstract | ||
|---|---|---|
We discuss a discrete optimization problem that arises in data analysis from the binarization of categorical attributes. It can be described as the maximization of a function F(l1(x), l2(x)), where l1(x) and l2(x) are linear functions of binary variables x ∈ {0,1}n, and F : R2 → R. Though this problem is NP-hard, in general, an optimal solution x* of it can be found, under some mild monotonicity conditions on F, in pseudo-polynomial time. We also present an approximation algorithm which finds an approximate binary solution xε, for any given ε 0, such that F(l1 (x*), l2(x*)) - F(l1 (xε), l2(xε)) n log n + 2C/√εn) operations. Though in general C depends on the problem instance, for the problems arising from [en]binarization of categorical variables it depends only on F, and for all functions considered we have C ≤ 1/√2. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.dam.2004.06.006 | Discrete Applied Mathematics |
Keywords | Field | DocType |
linear function,general c,feature generation,mild monotonicity condition,useful disjunction,n log n,approximation algorithm,categorical predicate,binary variable,approximate binary solution,data analysis,approximate discrete optimization algorithm,function f,categorical attribute,optimal solution,problem instance,machine learning,binary optimization,discrete optimization problem,categorical variable,discrete optimization | Discrete mathematics,Monotonic function,Approximation algorithm,Combinatorics,Discrete optimization,Categorical variable,Algorithm,Linear function,Time complexity,Mathematics,Maximization,Binary number | Journal |
Volume | Issue | ISSN |
144 | 1-2 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.39 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Boros | 1 | 1779 | 155.63 |
| Vladimir Menkov | 2 | 82 | 9.22 |