Article

A Combinatorial Bound for Linear Programming and Related Problems

Authors:

Micha Sharir,

Emo WelzlAuthors Info & Claims

STACS '92: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science

Pages 569 - 579

Published: 13 February 1992 Publication History

Abstract

No abstract available.

Cited By

View all

Xie MChen TWong RBoncz PManegold SAilamaki ADeshpande AKraska T(2019)FindYourFavoriteProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3320215(2017-2020)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3320215
Xie MWong RLi JLong CLall ADas GJermaine CBernstein P(2018)Efficient k-Regret Query Algorithm with Restriction-free Bound for any DimensionalityProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196903(959-974)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196903
Elbassioni KDumitrescu A(2017)Computational Geometry Column 66ACM SIGACT News10.1145/3173127.317313848:4(57-74)Online publication date: 13-Dec-2017
https://dl.acm.org/doi/10.1145/3173127.3173138
Show More Cited By

A Combinatorial Bound for Linear Programming and Related Problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization

Recommendations

A discrete gravitational search algorithm for solving combinatorial optimization problems

Metaheuristics are general search strategies that, at the exploitation stage, intensively exploit areas of the solution space with high quality solutions and, at the exploration stage, move to unexplored areas of the solution space when necessary. The ...
A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

A heuristic framework for a class of robust optimization problems is proposed.The heuristic framework explores dual information.The heuristic is successfully applied to solve two robust optimization problems.The heuristic is able to outperform a widely ...
Evolving heuristically difficult instances of combinatorial problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

When evaluating a heuristic for a combinatorial problem, randomly generated instances of the problem may not provide a thorough exploration of the heuristic's performance, and it may not be obvious what kinds of instances challenge or confound the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STACS '92: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science

February 1992

567 pages

ISBN:3540552103

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 13 February 1992

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xie MChen TWong RBoncz PManegold SAilamaki ADeshpande AKraska T(2019)FindYourFavoriteProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3320215(2017-2020)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3320215
Xie MWong RLi JLong CLall ADas GJermaine CBernstein P(2018)Efficient k-Regret Query Algorithm with Restriction-free Bound for any DimensionalityProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196903(959-974)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196903
Elbassioni KDumitrescu A(2017)Computational Geometry Column 66ACM SIGACT News10.1145/3173127.317313848:4(57-74)Online publication date: 13-Dec-2017
https://dl.acm.org/doi/10.1145/3173127.3173138
Grauman KLearned-Miller ETorralba AZisserman A(2017)Guest EditorialIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2017.266385939:4(625-626)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPAMI.2017.2663859
Chin TPurkait PEriksson ASuter D(2017)Efficient Globally Optimal Consensus Maximisation with Tree SearchIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2016.263153139:4(758-772)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPAMI.2016.2631531
Das SNandy ASarvottamananda S(2016)Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex ConstraintsProceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 960210.1007/978-3-319-29221-2_11(126-138)Online publication date: 18-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-319-29221-2_11
Har-Peled SRaichel B(2015)Net and PruneJournal of the ACM10.1145/283123062:6(1-35)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2831230
Gärtner BCheng SDevillers O(2014)Sampling with Removal in LP-type ProblemsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582121(511-518)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582121
Har-Peled SRaichel BBoneh DRoughgarden TFeigenbaum J(2013)Net and pruneProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488684(605-614)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488684
Brandenberg RKönig S(2013)No Dimension-Independent Core-Sets for Containment Under HomotheticsDiscrete & Computational Geometry10.1007/s00454-012-9462-049:1(3-21)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1007/s00454-012-9462-0
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

A discrete gravitational search algorithm for solving combinatorial optimization problems

A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

Evolving heuristically difficult instances of combinatorial problems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations