Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Maryam Kamgarpour, Baiwei Guo
2021
Journal Articles

Abstract

We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the European Journal of Operational Research. We point out where this error originates from in the proof of the main theorem. (C) 2020 The Author(s). Published by Elsevier B.V.

Official source

https://infoscience.epfl.ch/entities/publication/44c11582-b6ad-4b6b-877a-77f68f7ef331

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Maryam Kamgarpour, Baiwei Guo
2021
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/44c11582-b6ad-4b6b-877a-77f68f7ef331

About this result

Related concepts (18)

Mathematical proof

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation".

Constructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existence proof or pure existence theorem), which proves the existence of a particular kind of object without providing an example. For avoiding confusion with the stronger concept that follows, such a constructive proof is sometimes called an effective proof.

Proof theory

Proof theory is a major branch of mathematical logic and theoretical computer science within which proofs are treated as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of a given logical system. Consequently, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

Related publications (31)

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Graph Chatbot

SC-TPTP: An Extension of the TPTP Derivation Format for Sequent-Based Calculus

Orthologic with Axioms

Non-planarity of Markoff graphs mod p