{"entities":{"Q2768313":{"pageid":2779052,"ns":120,"title":"Item:Q2768313","lastrevid":47735029,"modified":"2026-01-02T13:49:34Z","type":"item","id":"Q2768313","labels":{"en":{"language":"en","value":"Approximating coloring and maximum independent sets in 3-uniform hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1699242"}},"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":"Q2768313$85FB6285-D15C-4FFE-9DFD-586D0F2756B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dd30ef5940417a0e4396b52a8f4df2e794b7095","datavalue":{"value":"0999.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$8D58CDD1-BF5A-4E08-9C8F-79783F49C919","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768313$59C0241F-F604-4627-83A1-0C6181A66FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0d7d75dca91c5d3ed36df4b4ea1d542c410ee50","datavalue":{"value":{"entity-type":"item","numeric-id":2765959,"id":"Q2765959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768313$C2A3F978-2A35-4BFF-8189-47CDE2DD7201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502bbb6d3842faa7531646862d34737b11134d06","datavalue":{"value":{"entity-type":"item","numeric-id":1584432,"id":"Q1584432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768313$72DA6566-0130-4EA4-A489-27E6FCF7E3EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ace5781d14ecf75d42ee9c3dff2c13074619ad7f","datavalue":{"value":{"time":"+2002-03-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2768313$F97BFFAF-2848-4027-9D05-B980613A389C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$F0BB880B-194D-4C1F-BD06-73C77754E1EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$CE475649-9B55-45D7-B488-7EF678C56EAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$DBE5CFF0-F5DE-4B5D-A1AA-3FBF32CEE2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$89ABE9B7-74F2-481C-BE7D-F7B5F243B115","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bb08d1175f475b377ec4652f9926e1f75166cc62","datavalue":{"value":"1699242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768313$C3F063BA-7236-4381-BF9B-4BBDCBCC7667","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768313$DCC07C90-DE48-4E81-95DE-47A99FE4ED56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768313$87760D84-B810-4CF8-8B95-FC7864C209D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"370afb08886d454ad02a3e32ab188f88b9fed55c","datavalue":{"value":"hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768313$F520C011-92F7-466C-BEE2-DBC31EF346EB","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":"Q2768313$EF9D7B95-520A-45C5-B365-9EABF4BA31C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64ccb59eeb8591bb48e8fd19e00d83288afb340a","datavalue":{"value":{"text":"Approximating coloring and maximum independent sets in 3-uniform hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2768313$67A73BE0-1657-4730-BD78-7F6ADB545AB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"982cf917dd3c3fa25dce0336a5dcdfcfd200d55d","datavalue":{"value":"In this 2-page note the authors propose approximation algorithms for coloring and independent set problems in 3-uniform hypergraphs. First, they discuss an algorithm for finding a large independent set in an \\(n\\)-vertex hypergraph with independent set of size \\(\\geq\\gamma n\\), for a constant \\(\\gamma> 0\\). Then they use this algorithm as a subroutine of an algorithm for coloring 3-uniform 2-colorable hypergraphs in \\(\\widetilde O(n^{1/5})\\) colors, thus improving the best currently known \\(\\widetilde O(n^{9/41})\\) algorithm. Finally, they show how to improve these algorithms using the local ratio approach. Due to space limits they present only brief outlines of their results.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768313$DD53DEFC-0266-4A3D-B502-03AEB95D1582","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768313$010CD1E0-74B5-4043-AECF-144DA0F8981A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6177b0d990ae29734f5324918ad89097fcb8ff97","datavalue":{"value":{"entity-type":"item","numeric-id":2765960,"id":"Q2765960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce3e930eaff268ea157fdabe0d5937b4b7a6b8e6","datavalue":{"value":{"amount":"+0.9378236532211304","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":"Q2768313$801EA8E6-40A0-4A70-8D60-A14C0F2ED14A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"072ccf319eeb7469ac38faed9e568ad860038720","datavalue":{"value":{"entity-type":"item","numeric-id":4252044,"id":"Q4252044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"482fa70b4d30cd2a18dd6e01d482324d769f0c9e","datavalue":{"value":{"amount":"+0.8761611580848694","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":"Q2768313$B04A004E-D94D-47E8-AE7A-2D7695C206B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2803e5a07fcc4cfd536be4358dfc96be6f071806","datavalue":{"value":{"entity-type":"item","numeric-id":4305670,"id":"Q4305670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"482fa70b4d30cd2a18dd6e01d482324d769f0c9e","datavalue":{"value":{"amount":"+0.8761611580848694","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":"Q2768313$6DBA3516-DBD3-49A1-B0A5-7DFB6F60163E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad302b9f9c678b9cb9fe135c0f4196ec3262900a","datavalue":{"value":{"entity-type":"item","numeric-id":4820902,"id":"Q4820902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1e670618d4a3db6b22ebf6748437732eefcf237","datavalue":{"value":{"amount":"+0.861551821231842","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":"Q2768313$4FD6589E-5367-4CB9-81D0-7DFA2127DA57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"476a35377a62dff554fa7daa0a2e68f361d599f1","datavalue":{"value":{"entity-type":"item","numeric-id":3599156,"id":"Q3599156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61acccdecd8c85aa8a2f491f2ddfe7b2be8c7929","datavalue":{"value":{"amount":"+0.8428799510002136","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":"Q2768313$1FDE8473-269D-405C-AE36-E5B32363E4D6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2768313","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2768313"}}}}}