skip to main content
Guest
e-Shelf
My Account
Sign out
Sign in
This feature requires javascript
Tags
e-Journals
e-Books
Databases
USP Libraries
Help
Help
Language:
English
Spanish
Portuguese (Brazil)
This feature required javascript
This feature requires javascript
Primo Search
General Search
General Search
Physical Collection
Physical Collections
USP Intelectual Production
USP Production
Search For:
Clear Search Box
Search in:
General Search
Or select another collection:
Search in:
General Search
Advanced Search
Browse Search
This feature requires javascript
Resource type
criteria input
anywhere in the record
in the title
as author/creator
in subject
Creation Date
lsr01
lsr02
lsr03
lsr04
Supervisor
Show Results with:
in the title
Show Results with:
anywhere in the record
in the title
as author/creator
in subject
Creation Date
lsr01
lsr02
lsr03
lsr04
Supervisor
Show Results with:
criteria input
that contain my query words
with my exact phrase
starts with
Show Results with:
Index
criteria input
AND
OR
NOT
This feature requires javascript
On semantic cutting planes with very small coefficients
Lauria
,
Massimo
; Thapen, Neil
Information processing letters, 2018-08, Vol.136, p.70-75
[Peer Reviewed Journal]
Elsevier B.V
Full text available
Citations
Cited by
View Online
Details
Reviews & Tags
More
Times Cited
This feature requires javascript
Actions
Add to e-Shelf
Remove from e-Shelf
E-mail
Print
Permalink
Citation
EasyBib
EndNote
RefWorks
Delicious
Export RIS
Export BibTeX
This feature requires javascript
Title:
On semantic cutting planes with very small coefficients
Author:
Lauria
,
Massimo
;
Thapen, Neil
Subjects:
Cutting planes
;
Proof complexity
;
Theory of computation
Is Part Of:
Information processing letters, 2018-08, Vol.136, p.70-75
Description:
Cutting planes proofs for integer programs can naturally be defined both in a syntactic and in a semantic fashion. Filmus et al. (STACS 2016) proved that semantic cutting planes proofs may be exponentially stronger than syntactic ones, even if they use the semantic rule only once. We show that when semantic cutting planes proofs are restricted to have coefficients bounded by a function growing slowly enough, syntactic cutting planes can simulate them efficiently. Furthermore if we strengthen the restriction to a constant bound, then the simulating syntactic proof even has polynomially small coefficients. •Semantic cutting planes proofs are stronger than syntactic one [FHL'16].•If coefficients in the semantic proof are small enough, we can efficiently simulate it with a syntactic proof.•We prove an efficient form of implicational completeness, with respect to coefficient size.
Publisher:
Elsevier B.V
Language:
English
This feature requires javascript
This feature requires javascript
Back to results list
Previous
Result
15
Next
This feature requires javascript
This feature requires javascript
Searching Remote Databases, Please Wait
Searching for
in
scope:(USP_PRODUCAO),scope:(USP_EBOOKS),scope:("PRIMO"),scope:(USP),scope:(USP_EREVISTAS),scope:(USP_FISICO),primo_central_multiple_fe
Show me what you have so far
This feature requires javascript
This feature requires javascript