{"entities":{"Q1064975":{"pageid":1075727,"ns":120,"title":"Item:Q1064975","lastrevid":66664860,"modified":"2026-04-12T11:39:52Z","type":"item","id":"Q1064975","labels":{"en":{"language":"en","value":"A setup heuristic for interval orders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3922403"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$D4C5E0B6-EEB0-41A5-B153-9F002C446227","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eeb2f2823f317b9dbf20e54ef5bab88a3479d7d5","datavalue":{"value":{"text":"A setup heuristic for interval orders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1064975$49DB2EE0-E64F-46BD-9821-DEC7B1C798E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"96c313960146c601dafcc43ec4120c68e1fbcecb","datavalue":{"value":"0576.90097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$C48C4FCA-822C-417B-A6F6-0C55D1F56712","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"837fa15e7a3a8f3d0b7ea3ec523e6e27baf36456","datavalue":{"value":"10.1016/0167-6377(85)90027-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$1C872163-4A49-434C-AD5D-276ADD3E8173","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a4e46d7f82b5bd7ae5274f9e30daac89c5398cc","datavalue":{"value":{"entity-type":"item","numeric-id":185691,"id":"Q185691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$0502F8B7-C0D9-49C2-BBC2-EF1013274004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f8b2ce9c9f99ff6b75357124c91b50e0e1c58b6","datavalue":{"value":{"entity-type":"item","numeric-id":751494,"id":"Q751494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$0AC395F1-3342-4245-8382-72A1BF6DEC3C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$0D734E4C-BA0E-4888-B7F7-C6985F12780A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1064975$9B8AE75B-E729-4074-806E-B7E8C727290E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a662a991591eb794d6336b723c46479f9fdce8ed","datavalue":{"value":"The setup minimization problem asks to determine a sharp lower bound for the number of incomparable adjacent pairs of elements that may occur in linear extensions of a given ordered set. This problem is known to be difficult in general. In particular, no efficient exact solution method is available for the class of interval orders. Taking advantage of a suitable decomposition property of this class, we present a simple greedy heuristic which can be shown to achieve never worse than twice the optimum. To date, the class of interval orders is the only class known which allows an efficient approximate solution but for which no efficient exact algorithm has been found.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064975$9CE13984-BFCC-4FEB-97EB-4C244FCC4ADB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$39FCAA32-4F28-4A1A-8708-21DA1878F096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7dfd8303bd13aea2e4b7120171f58bea1dddf5e5","datavalue":{"value":"91B08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$AD61FD35-8FD9-4B32-913F-33E50B37F132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"41797f091d2c1efd3accd53dd04e594e696bb107","datavalue":{"value":"06-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$944B0A4A-FCFD-42B9-9399-CCA49F5DC863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"306e8f65eab4f086795d9337f8e86ca94ed2db57","datavalue":{"value":"90B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$D5316CC5-D948-4571-BF81-111E480DF2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$89260050-8FB6-4015-96DC-11CB92304DD0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5a8f2d7be5c0d4b0be93f6d5054170ae050830c","datavalue":{"value":"3922403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$E7B625AF-A66A-4B5A-A616-9932EA4AAEF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2169ecfdfd621929a6527962d5eafbeaf72e2ac4","datavalue":{"value":"setup minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064975$9F203A24-EA6B-4199-B862-74B354AB5101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62d18420b0848a4c0300452d10ba1f75d74dc0e1","datavalue":{"value":"interval orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064975$22E957FE-05D5-4B13-BBD2-559731A7CB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd0ec47f2d4dab7908c2ebbe2726174dab4de56e","datavalue":{"value":"greedy heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064975$73A0502C-8A09-43AF-98C5-E3DB2DA7CF78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"028d7575356a848c42db22671846d41796656f4b","datavalue":{"value":"efficient approximate solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064975$BC4C4EF7-6DCD-4578-81EE-F934AF445B45","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$FEEBC3C5-C18D-47FA-BB38-C2E6A9A3713A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"91109fc4f73d2ec0807e8b9740a7cbb127f435db","datavalue":{"value":"https://doi.org/10.1016/0167-6377(85)90027-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1064975$51F29214-F165-4767-9330-86EABA154A49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"098197e922b48552a2bfbe147cb7e3359a81c1d6","datavalue":{"value":"W2064889167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064975$F937BB12-BC11-475C-848B-F62E421C95E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"433aacb3b753ddf861d4b3d2e5750f83f114a9ac","datavalue":{"value":{"entity-type":"item","numeric-id":4200070,"id":"Q4200070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$9A06A403-19B6-4F45-8846-E0AC90C34F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7719de6c339bb9d4088f30d5f516e35f5c2b87f","datavalue":{"value":{"entity-type":"item","numeric-id":3694689,"id":"Q3694689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$68294129-8754-4FC3-BF40-4750654F269F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c419329cf6a4ec59893cd2cee822bc47fc6dde6","datavalue":{"value":{"entity-type":"item","numeric-id":3910550,"id":"Q3910550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$C70169BA-720B-49C9-B8FE-8409F60EF25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c63844c2e38245fdc6612bce29c35b91b812a27","datavalue":{"value":{"entity-type":"item","numeric-id":3854618,"id":"Q3854618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$0784FDD0-8D74-4FC0-B88B-A4066AD86C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d4c3394fe33a803d44b9613be7e42b3f4c68ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3674720,"id":"Q3674720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$4E7E2A89-5267-4B3A-BB79-D8545078CAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccd9e091a9bae20d9f917fc646948f9bba2d344d","datavalue":{"value":{"entity-type":"item","numeric-id":5184958,"id":"Q5184958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064975$4DEECD8A-FBEC-4DEB-A2F1-23E7D5F6A97B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5d86aae12aefc2063e644a13214e0aef7d88a05","datavalue":{"value":{"entity-type":"item","numeric-id":3694689,"id":"Q3694689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67cc29a7103bbc4ff6f735850c3c5ea6d793bf56","datavalue":{"value":{"amount":"+0.8462514877319336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1064975$0867B3B4-E4C0-49A6-990A-DECE131EDC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d1ea9ec42a5be891d6a23bd42b73ebf686741b3","datavalue":{"value":{"entity-type":"item","numeric-id":1195865,"id":"Q1195865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea172e80cf2e5beca3ba483f59645e7abb8758eb","datavalue":{"value":{"amount":"+0.8449482321739197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1064975$D73EF894-FAFD-48F1-A532-FCBC2E128D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b49b094d207690d8b026361c80323fb4785687b6","datavalue":{"value":{"entity-type":"item","numeric-id":1183348,"id":"Q1183348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f0f228192c0c0f4fdaef06c7a362547664aa88","datavalue":{"value":{"amount":"+0.7931408882141113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1064975$43142170-8B67-452D-AA1B-0FF5F016E75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f092f593c4f508ede47fc18e246977186fd29ed","datavalue":{"value":{"entity-type":"item","numeric-id":1182058,"id":"Q1182058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c53fe56dfb2dd46b50831ac153e176b74c88032","datavalue":{"value":{"amount":"+0.7911605834960938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1064975$851883EA-6C63-4BF1-AB92-E690E8ACCD17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c2e50c3a2b7b4246a3161fc8a060403211ccee","datavalue":{"value":{"entity-type":"item","numeric-id":762183,"id":"Q762183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b382846d908acf4c178f55d4b8ac68b52592bbb","datavalue":{"value":{"amount":"+0.7854913473129272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1064975$2DB9773E-1361-413A-B05A-E17C79CC3FEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A setup heuristic for interval orders","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_setup_heuristic_for_interval_orders"}}}}}